【例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;
} 

贪心算法

贪心的实质是短期内的最优解，即每一步选择是该步骤的最优，作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 所以它不一定能得到最优解

典型的就是：

• 超市零钱问题（优先找面值较大的）
• 0-1背包问题（是按照性价比最高的选择-价值/重量（单位重量价格最大的选））
• 会议室问题，同一时间只能用一个会议室，能利用的会议室最多（按照会议室的使用结束时间排序，优先排按照时间顺序先结束的会议室）