系列文章目录
第一篇 【贪心算法】初步介绍
第二篇 【贪心算法】删数问题
第三篇 【贪心算法】排队打水 （此篇）
一、题目
1141. 【贪心算法】排队打水 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述：
有n（n<=1000）个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
输入：
输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
输出：
输出文件有两行，第一行为一种排队顺序，即1到n的一种排列（如果有多种方案，请输出字典序最小的方案）；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
样例输入：
10
56 12 1 99 1000 234 33 55 99 812
样例输出
3 2 7 8 1 4 9 6 10 5
532.00
二、思路
这是一道经典的贪心算法问题。题目意思是给你一个数列，在经过一定顺序的排列后，求出结果为a[1]*n+a[2]*(n-1)+a[3]*(n-2)+...+a[n]的s,并使其最小。
因此，只需要对a[i]进行从小到大的排序，再暴力求出结果就行了。但是，我们要先输出其原先的顺序，因此我就用二维数组记录--a[i][1]表示装水时间，a[i][2]代表原来i是第几个。
而排序具体如下：
for(int i=1;i<m;i++) { for(int j=i+1;j<=m;j++) { if(a[i][1]>a[j][1]) { swap(a[i],a[j]); } } }
如程序，我的整体排序方式是选择排序。当符合交换条件（后者时间比前者短），就swap（）。这个swap函数很厉害，可以把整个a[i]与a[j]交换；而且只需要iostream的头文件，也十分方便，值得计入笔记本当中！！！
最后，在输出a[i][2]的同时，进行计算。接着——
静待AC！
编辑
实际上，上述排序方式只是适应于初学者中的初学者，我们还可以用快排、归并排序、插入排序、桶排等等等等。当然，对于时间很短，数据不大的题目（例如此题），用上述的冒泡排序即可。
不过，用sort（）函数也不错。（关于sort函数，详见我的另一篇文章sort()函数详解）。
三、AC源程序
#include<bits/stdc++.h> using namespace std; int m,a[1005][3]; double s; int main() { cin>>m; for(int i=1;i<=m;i++) { cin>>a[i][1]; a[i][2]=i; } for(int i=1;i<=m-1;i++) { for(int j=i+1;j<=m;j++) { if(a[i][1]>a[j][1]) { swap(a[i],a[j]); } } } for(int i=1;i<=m;i++) { cout<<a[i][2]<<" "; s=s+a[i][1]*(m-i+1); } printf("\n%.2f",s/(m*1.0)); }
总结
以上就是今天要讲的内容，请各位点个赞再走！！！
