【例6.1】排队接水贪心算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【例6.1】排队接水贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【例6.1】排队接水

时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n
个人的平均等待时间最小。

【输入】
共两行，第一行为n(1≤n≤1000)；第二行分别表示第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
291.90

思路：

要想平均等待时间最短，那就让接水时间短人的先接水
首先是将接水时间排序，由于输出数据要求排队顺序，所以最好是用一个结构体储存排队顺序和时间。排序可以写一个排序函数，或者直接用自带的sort(begin,lenth,way)
示例10个人时，求平均时长：只有九个人需要等，sum/10, 可以首先想到用一个数组a存储每个人的等待时间（a[i]=a[i]+k[i].t）然后再将每个人都等待时间相加，但是也有简便的方法，排队时，只要没有接到水（k-i）的都需要等待即 sum+=k[i].t*（k-i）

#include <bits/stdc++.h>
using namespace std;
struct ti{
	int t; //存储接水时间 
	int i; //存储编号 
}t[1001];
bool s_sort(ti a,ti b){
	if(a.t<b.t) return  true;
	else return false;
} 
int main(){
	int k;
	double sum=0;
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>t[i].t;
		t[i].i=i;
	}
	sort(t+1,t+k+1,s_sort);  //完成排序并记录下标的值 ,降序排列 
	for(int i=1;i<=k;i++){
		cout<<t[i].i<<" ";
		if(i<k)
		sum+=t[i].t*(k-i);
	}
	cout<<endl;
	printf("%.2lf",sum/k);
	return 0;
}