ToB企服应用市场:ToB评测及商务社交产业平台

标题: 洛谷P1223 列队接水 [打印本页]

---

作者: 鼠扑    时间: 2024-8-5 16:32
标题: 洛谷P1223 列队接水
P1223 列队接水

题目描述

有 \(n\) 个人在一个水龙头前列队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 \(n\) 个人列队的一种序次，使得 \(n\) 个人的平均等候时间最小。
输入格式

第一行为一个整数 \(n\)。
第二行 \(n\) 个整数，第 \(i\) 个整数 \(T_i\) 表现第 \(i\) 个人的接水时间 \(T_i\)。
输出格式

输出文件有两行，第一行为一种平均时间最短的列队序次；第二行为这种分列方案下的平均等候时间（输出结果精确到小数点后两位）。
样例 #1

样例输入 #1

1. 10
2. 56 12 1 99 1000 234 33 55 99 812

复制代码

样例输出 #1

1. 3 2 7 8 1 4 9 6 10 5
2. 291.90

复制代码

提示

\(1\le n \leq 1000\)，\(1\le t_i \leq 10^6\)，不包管 \(t_i\) 不重复。
思路：

• 我们可以采取贪心的策略，将接水时间慢的人放在后面列队，那么后面的人的列队时间就较短，这是我们的直觉告诉我们的结果，并且，这也是贪心策略的局部最优解，我们只需要尽可能的将接水时间长的人排在后面接水，那么其他人等候的时间就会减少，到最终时，总的接水时间就会最少。
  
• 那么我们这种的接水策略是否能严格的数学证明呢？实在大部门的时候，我们贪心策略的思想，就黑白常正常的常识，只要我们举不出显着的反例来证明我们的策略不可行，我们就可以使用贪心策略，不过这题我们还真的可以来进行严格的数学证明我们这个策略的可行性。
  

证明策略的可行性

• 从这里也可以看出，贪心策略往往与排序是一起出现的，每次枚举最优的解法，最终到达最优的结果！
  

代码：

[code]#include#includeusing namespace std;struct people {        int t;        int id;}a[1005];//按接水时间来升序分列bool compare(people& a, people& b) {        return a.t < b.t;}int n;int main(){        cin >> n;        for (int i = 1; i > a.t;                a.id = i;        }        sort(a + 1, a + 1 + n, compare);        for (int i = 1; i

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4