贪心刷题2

题���来源：排队接水 - 洛谷

参考书目:《深入浅出程序设计竞赛（基础篇）》

解题思路：按照接水时间对人进行排序，这样能确保每个人的等待时间被最小化。因为如果一个接水时间长的人排在前面，他会增加后面所有人的等待时间；而接水时间短的人排在前面，则他对后面人的等待时间影响较小。

例子：假设有3个人排队接水，他们按接水时间升序排列后的接水时间分别为：

• 第1个人：T1 = 2分钟
• 第2个人：T2 = 3分钟
• 第3个人：T3 = 5分钟

  计算总等待时间时，我们需要计算每个人在他之前所有人接水所耗费时间的总和。每个人的等待时间计算如下：

  • 第1个人前面没有任何人，所以他的等待时间为0分钟。
  • 第2个人等待的是第1个人接水的时间，所以他的等待时间为T1 = 2分钟。
  • 第3个人等待的是第1个人和第2个人接水的时间总和，所以他的等待时间为T1 + T2 = 2 + 3 = 5分钟。

    现在我们来计算总等待时间sum：

    • 第1个人的等待时间：0分钟
    • 第2个人的等待时间：2分钟
    • 第3个人的等待时间：5分钟

      总等待时间sum是这些等待时间的总和：0 + 2 + 5 = 7分钟。

      平均等待时间是总等待时间除以人数，即7 / 3 ≈ 2.33分钟。

      • 对于第1个人（i = 1），(n - i) 是 3-1= 2，意味着他的接水时间会对后面2个人产生影响。
      • 对于第2个人（i = 2），(n - i) 是 3-2= 1，意味着他的接水时间会对后面1个人产生影响。
      • 对于第3个人（i = 3），(n - i) 是 3-3= 0，意味着他的接水时间会对后面0个人产生影响。

        这样，每个人的接水时间对于等待时间的贡献是累积的，而不需要为每个人单独累加前面所有人的接水时间。这是一种更有效率的计算总等待时间的方法。

        #include#includeusing namespace std;struct water {    int num, time;}p[1010];bool cmp(water a, water b){    if (a.time != b.time)    {        return a.time > n;    for (int i = 1; i > p[i].time;        p[i].num = i;    }    sort(p + 1, p + n + 1, cmp);    for (int i = 1; i