题目描述
有 \(n\) 个人在一个水龙头前排队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 \(n\) 个人排队的一种顺序，使得 \(n\) 个人的平均等待时间最小。
证明
如果要让所有人等待时间最短，那么就让打水速度快的人在前面
- \(Part\) \(1\)
因为如果将等待时间较长的人往前排，他们就会占据水龙头的时间较长，后面的人等待的时间更长。
贪心算法的思路就是每次选择等待时间最短的人往前排。这样做的好处是，等待时间较短的人能够尽快接水，释放出水龙头，让后面的人能够更早开始接水，从而减少总体的平均等待时间。
在上面的代码中，我们使用了贪心策略，将等待时间从小到大进行排序，并按照这个顺序建立排队列。这样，等待时间较短的人会尽早进入队列，从而减少了总体的平均等待时间。
- \(Part\) \(2\)
我们可以使用数学证明的方法来做这道题：
有 \(x\) 人，每个人打水时间为 \(x_{i}\) ，如果让打水速度快的人在前面,那么总时间为：
\[x_{1} (n-1) \times x_{2} (n-2) \cdots x_{i} (n-i) \]如果要总时间最短，就让 \(x_{1} > x_{2} > x_{3} > \cdots > x_{n}\)
所以，要让平均排队时间最小，就要让打水快的人往前排
- \(Part\) \(3\)
好的，让我们使用反证法来证明这个结论。
假设存在一种排队顺序，其中等待时间较长的人往前排，但是这种排队顺序的平均等待时间最小。
首先，我们先说明一个引理：
引理： 在任何一个排队顺序中，如果我们交换了两个连续的人的位置，那么平均等待时间要么保持不变，要么减少。
证明：设原始排队顺序为 \(A, B, C, D, E, F\)，其中 \(A\) 的等待时间最长。交换 \(B\) 和 \(C\) 的位置，得到新的排队顺序为 \(A, C, B, D, E, F\)。我们假设交换位置后的新平均等待时间比原始平均等待时间更长。那么有：
\[\text{等待时间总和}(A) + \text{等待时间总和}(B,C) < \text{等待时间总和}(A, B, C) \]但是，如果我们将 \(C\) 插入到 \(A\) 和 \(B\) 之间的位置，也就是得到新的排队顺序 \(A, C, B, D, E, F\)，根据平均等待时间的定义，我们可以得到：
\[\text{等待时间总和}(A, C) + \text{等待时间总和}(B) < \text{等待时间总和}(A, B, C) \]与假设矛盾。所以，我们的假设是错误的，交换的位置并不会导致平均等待时间变长。
现在，我们使用反证法来证明假设的排队顺序不会使平均等待时间最小。
假设我们按照等待时间从小到大进行排序，依次为 \(A, B, C, D, E, F\)。其中，\(A\) 的等待时间最短，\(F\) 的等待时间最长，按照假设的排队顺序，我们将 \(A\) 放在了最后的位置。
现在，我们考虑将 \(A\) 移动到最前面的情况，即排队顺序为 \(A, B, C, D, E, F\)。
根据引理，我们知道这个新的排队顺序的平均等待时间要么保持不变，要么减少就平均等待时间而言，我们可以计算出初始排队顺序和新排队顺序的总等待时间，并比较两者的大小：
- 初始排队顺序的总等待时间为 \(\text{等待时间}(A) + \text{等待时间}(B, C, D, E, F)\)
- 新排队顺序的总等待时间为 \(\text{等待时间}(A, B, C, D, E, F)\)
如果新排队顺序的总等待时间小于初始排队顺序的总等待时间，则说明新排队顺序的平均等待时间也会更小。因此，假设的排队顺序不会平均等待时间最小。
根据反证法的原理，我们可以得出结论：要使平均排队时间最小，就要让打水快的人往前排。
算法原理
- 贪心算法
为了找出平均等待时间最小的排队顺序，我们可以使用贪心算法。贪心算法的基本思想是在每一步选择局部最优解，最终得到全局最优解。
我们可以按照等待时间从小到大的顺序给人员进行排序。这样，等待时间最短的人员先接水，等待时间稍长一些的人员后接水。这样安排，可以使得整体的等待时间减少。
代码实现
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define N 1010
int n,a[N]={0,},b[N];
double t1,t2;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
t1+=a[i-1];
t2+=t1;
for(int j=1;j<=n;j++)
{
if(a[i]==b[j])
{
cout<<j<<" ";
b[j]=0;
}
}
}
t2/=n;
printf("\n");
printf("%.2f",t2);
return 0;
}
tips
注意题目中的坑——两位小数
-
cout<<fixed<<setprecision(2)(头文件#include<iomanip>); -
printf("%.2f",a)（头文件就不说了）