【例6.1】排队接水 贪心算法

发布时间:2024年01月09日

【例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背包问题(是按照性价比最高的选择-价值/重量(单位重量价格最大的选))
  • 会议室问题,同一时间只能用一个会议室,能利用的会议室最多(按照会议室的使用结束时间排序,优先排按照时间顺序先结束的会议室)
文章来源:https://blog.csdn.net/m0_46183615/article/details/135486527
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。