首页 > 代码库 > 贪心1--排队打水问题
贪心1--排队打水问题
贪心1--排队打水问题
一、心得
二、题目及分析
题目意思:有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
分析:看题目意思,要使每个人平均等待时间最小,当然是接水时间小的排在前面了，因此解法如下。
1、读入n个人接水时间。
2、对等待时间A数组进行排序，序号数组B同时进行排序。这里数据n为20000，因此，必须用快排才行，同时要注意的是，排序的时候要注意等待时间是一样的时候，序号前的要排在前面，所以要用到双关健排序。
3、对每个接水时间T进行累加S即S:=s+a[i]，就是下一个人的等待时间了。对每个等时间S进行累加ZS，ZS就总等待时间了。
三、代码及结果
代码中的n为100
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 int main(){ 6 int n,r; 7 cin>>n>>r; 8 int a[100]; 9 for(int i=1;i<=n;i++){ 10 cin>>a[i]; 11 } 12 sort(a+1,a+n+1); 13 14 //水龙头 15 int tap[100]; 16 memset(tap,0,sizeof(tap)); 17 int j=1; 18 int sum=0; 19 for(int i=1;i<=n;i++){ 20 if(j==r+1) j=1; 21 tap[j]+=a[i]; 22 sum+=tap[j]; 23 j++; 24 } 25 cout<<sum<<endl; 26 return 0; 27 }
贪心1--排队打水问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。