题意

有n个人排队到r个水龙头去打水,他们装满水桶的时间t1,t2,...,tn为整数且各不相等,应如何安排他们的打水顺序才能使他们花费的总时间最少?

每个人打水的时间 = 排队的时间 + 实际打水的时间,本题假设一个人打好水,排在他后面的人接着打水的这个切换过程不消耗时间。

比如,有2个人A和B,他们打水的时间分别是3和2,只有1个水龙头,这时,如果A先打水,B后打水,那么A和B打水的时间分别为3、3+2(B排队3分钟)。

因此,所有人打水的总时间就是每个人的打水时间及每个人的排队时间的总和。

输入格式

第1行,两个整数n(1<=n<=500)和r(1<=r<=100)。

第2行,n个正整数t1,t2,...,tn,(1<=ti<=1000)表示每个人装满水桶的时间。


输出格式

1行,一个正整数,表示他们花费的最少总时间。

样例输入

 4 2
 2 6 4 5

样例输出

 23

题解

运用优先队列 + 贪心算法

==花费的时间=每个人接水的时间+每个人排队等待的时间==

因为每个人的接水时间已经是固定的了,那么要确定最少的花费时间

就取决于让每个人排队等待的时间最少

这样让接水时间少的人先接,就能保证后面排队的人用时最短

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

priority_queue<int, vector<int>, greater<int> > q;  //小根堆,队头总是为最小元素
vector<int> a[N]; 	 

int main()
{
	int n, r, sum_do = 0, sum_wait = 0;
	cin >> n >> r;
	
	for(int i = 1, x; i <= n; i++)  //先计算所有人的打水时间,并压入小根堆(优先队列)
	{
		cin >> x;
		sum_do += x;
		q.push(x);
	}
		
	int t = 1;
	for(int i = 1; i <= n; i++)   //再分别让最小值循环插入r个水龙头
	{
		a[t].push_back(q.top());
		q.pop();
		t = t % r + 1;   //该行可构成循环插入
	}	
	
	
	for(int i = 1; i <= r; i++)
	{
		int temp = 0;
		for(int j = 0; j < a[i].size() - 1; j++)  //除了每个水龙头的最后一个人,其他的等待时间都要加上
		{
			temp += a[i][j];    //逐个加上
			sum_wait += temp;
		}
	}
		
	cout << sum_do + sum_wait;  //总时间 = 打水时间 + 等待时间
	return 0;
} 
上一篇 下一篇