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<algorithm>
#include<iostream>
using 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 <= n; i++) {
		cin >> a[i].t;
		a[i].id = i;
	}
	sort(a + 1, a + 1 + n, compare);
	for (int i = 1; i <= n; i++) {
		cout << a[i].id << " ";
	}
	cout << endl;
	double sum = 0;
    //这里为什么要✖(n-i)呢，因为第一个人洗澡的时候，后面n-1个人都要等它，第二个人，后面的n-2个人又要等他
	for (int i = 1; i <= n - 1; i++) sum += a[i].t*(n-i);
	double average = sum / n;
	printf("%.2lf", average);
	return 0;
}

部分代码的解释:

计算sum的部分涉及到如下的代码段：

double sum = 0;
for (int i = 1; i <= n - 1; i++)
    sum += a[i].t * (n - i);

这段代码的目的是计算加权平均数的值，其具体含义是在对人员按照t属性排序后，计算每个人在队列中的等待时间乘以其后面人数的总和。让我们分析一下为什么要乘以(n - i)：

排序的影响：
- 数组 a[] 中的人员按照 t 属性从小到大排序。
- 排序后，a[i].t 表示第 i 个人的处理时间。
等待时间的计算：
- 在排序后的顺序中，如果第 i 个人在队列中，那么他前面有 i - 1 个人，因此他的等待时间就是前面所有人的处理时间之和。
加权求和的原理：
- 对于第 i 个人，他的等待时间为 a[i].t * (n - i)。这里 (n - i) 表示的是他后面的人数，因为他后面的每个人都要等待他的处理时间。
计算总和：
- sum += a[i].t * (n - i) 就是把每个人的等待时间乘以后面的人数加起来，得到总的加权等待时间之和。
最终的平均值：
- average = sum / n 就是将这个加权等待时间之和除以总人数 n，得到的是每个人的平均等待时间。

因此，乘以 (n - i) 的操作是为了正确地计算每个人的等待时间对整体加权平均数的贡献，确保了按照题目要求正确计算平均值。