排队打水问题（信息学奥赛一本通贪心算法）

---

题目描述：

 有n个人排队到r个水龙头打水，他们装满水的时间为 t1,t2,………tn为整数且各不相等，
 应如何安排他们打水顺序才能使他们花费时间最少（含等待时间）？

【算法分析】
 由于排队时，越靠前面的计算次数越多，因此时间越小的排队越靠前得出结果越小，所以可以用贪心算法解答。
 步骤如下：
（1）按时间顺序从小到大排序（sort函数)；
（2）将排序后的时间按顺序依次放到每个水龙头的队列中；
（3）统计并输出。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int MAXN=1000;
 6 int a[MAXN],s[MAXN];
 7 int main(){
 8     int n,r,j=0,minx=0;
 9     memset(s,0,sizeof(s));
10     cin>>n>>r;    
11     for(int i=0;i<=n;i++)
12         cin>>a[i];
13     sort(a+1,a+n+1);                //对所有的时间排序 
14     for(int i=1;i<=n;i++){
15         j++;
16         if(j==r+1)    
17             j=1;                //前r个人人为一组，第r+1个人回到第一个水龙头
18         s[j]+=a[i];                //加上等待时间
19         minx+=s[j];             //累加 
20     }
21     cout<<minx<<endl;
22     return 0;
23 } 

---

 相似题目：https://www.luogu.com.cn/problem/P1223

---

简单数学证明

摘自：https://www.luogu.com.cn/problemnew/solution/P1223

首先我们要排的是所有的元素，但是为什么是从小到大呢？？？

排队总是象征要排序，每个元素在此序列下都要满足条件，也就是从中拿出两个相邻元素同样满足条件：

于是设：ai 和 bi且ai<bi

那么针对这两个元素：就有两种排列情况：

　　1.ai排在bi前面那么有总时间：t1=ai+ai+bi.

　　2.bi排在ai前面那么有总时间：t2=bi+bi+ai.

于是由ai<bi得出 t1<t2—》变一下式子—》ai+ai+bi<bi+bi+ai;

再化简不等式得出ai<bi

于是得出结论：当ai在bi前面时，时间为最小值。

于是反推回总体，两两相较，那么越小的应该越排在前面，以至于总时间越小

---