排队打水问题——贪心

问题描述
有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？
输入格式
第一行n，r (n<=500,r<=75)
第二行为n个人打水所用的时间Ti (Ti<=100)；
输出格式
最少的花费时间
样例输入
3 2
1 2 3
样例输出
7

思路：这道题关键就是理解题意
这道题最后要求
花费的时间=每个人接水的时间+每个人排队等待的时间 
确定了这个就很好求了
这个题的贪心策略：
因为每个人的接水时间已经是固定的了，那么要确定最少的花费时间
就取决于让每个人排队等待的时间最少 
这样让接水时间少的人先接,就能保证后面排队的人用时最短.

#include
using namespace std;int main()
{int n,r;scanf("%d %d",&n,&r);int i;int a[n];//记录每个人接水的时间 for(i=0;i=n)//当水龙头数大于总人数时情况单独讨论 {printf("%d",accumulate(a,a+n,0));//直接将每个人的接水时间加和 return 0;}while(1){if(p==n)//当所有人都接到水后跳出循环 {tim1+=(accumulate(b,b+r,0));break;}for(i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！