洛谷P1223 排队接水
P1223 排队接水题目描述
有 \(n\) 个人在一个水龙头前排队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 \(n\) 个人排队的一种顺序，使得 \(n\) 个人的平均等待时间最小。
输入格式
第一行为一个整数 \(n\)。
第二行 \(n\) 个整数，第 \(i\) 个整数 \(T_i\) 表示第 \(i\) 个人的接水时间 \(T_i\)。
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
样例 #1
样例输入 #1
10
56 12 1 99 1000 234 33 55 99 812样例输出 #1
3 2 7 8 1 4 9 6 10 5
291.90提示
\(1\le n \leq 1000\)，\(1\le t_i \leq 10^6\)，不保证 \(t_i\) 不重复。
思路：
[*]我们可以采取贪心的策略，将接水时间慢的人放在后面排队，那么后面的人的排队时间就较短，这是我们的直觉告诉我们的结果，并且，这也是贪心策略的局部最优解，我们只需要尽可能的将接水时间长的人排在后面接水，那么其他人等待的时间就会减少，到最终时，总的接水时间就会最少。
[*]那么我们这种的接水策略是否能严格的数学证明呢？其实大部分的时候，我们贪心策略的思想，就是非常正常的常识，只要我们举不出明显的反例来证明我们的策略不可行，我们就可以使用贪心策略，不过这题我们还真的可以来进行严格的数学证明我们这个策略的可行性。
证明策略的可行性
[*]从这里也可以看出，贪心策略往往与排序是一起出现的，每次枚举最优的解法，最终达到最优的结果！
代码：
#include#includeusing namespace std;struct people { int t; int id;}a;//按接水时间来升序排列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 用心讨论，共获提升！ 谢谢分享，试用一下 谢谢分享，辛苦了 感谢分享 收藏一下 不知道什么时候能用到 感谢，下载保存了 分享、互助 让互联网精神温暖你我 前排留名，哈哈哈 谢谢分享，辛苦了 新版吗？好像是停更了吧。 感谢分享，学习下。 不错，里面软件多更新就更好了 用心讨论，共获提升！ 不错，里面软件多更新就更好了 懂技术并乐意极积无私分享的人越来越少。珍惜 谢谢分享，辛苦了 收藏一下 不知道什么时候能用到 不错，里面软件多更新就更好了 新版吗？好像是停更了吧。
页:
[1]
2