排队打水问题——贪心

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

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

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,r;
	scanf("%d %d",&n,&r);
	
	int i;
	int a[n];//记录每个人接水的时间 
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	sort(a,a+n);//排序,从小到大的顺序接水 
	
	int b[r]={0};//表示当前水龙头接水的人还有多长时间接完 
	int tim1,tim2;//表示接水总时间和等待总时间 
	tim1=tim2=0;
	
	int p=0,min;
	if(r>=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<r;i++)
		{
			if(b[i]==0)
			{
				b[i]=a[p++];
			}
		}
		min=*min_element(b,b+r);//找到当前接水的人中剩余最短的时间 

		for(i=0;i<r;i++)
		{
			b[i]-=min;
		}

		tim1+=min*r;
		tim2+=min*(n-p);
	}
	printf("%d",tim1+tim2);
	return 0;
}