题目描述
题目描述
有n个人排队到r个水龙头去打水,他们装满水桶的时间t1、t2…tn为整数且各不相等,应如何安排他们的打水顺序才能使他们总共花费的时间最少?
数据规模和约定
其中80%的数据保证n$<=$10
输入格式
第一行n,r (n< =500,r< =75)
第二行为n个人打水所用的时间$T_{i}$ ($T_{i}$< =100);
输出格式
最少的花费时间
样例输入
3 2
1 2 3
样例输出
7
注:一共2个水龙头,1和2先用,花费时间3,然后1用完了3马上用,花费时间4(等待1分钟,自己用3分钟),总共用时7分钟最小。
分析
每个人用的$时间t=等待时间+打水时间$, 打水时间固定,所以要让所用花费时间最小,就应该让所有人的等待时间最小。所以需要从小到大排序,把时间小的放在前面。
有r个水龙头就要模拟这r个水龙头,先从小到大取出r个人放进去,然后取出打水时间最小的拿出来,再放入等待队列中打水时间最小的,每次都要对r个水龙头重新排序。
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 510;
int n,r,ans,a[N];
vector<int> v;
priority_queue<int,vector<int>,greater<int> > q;
int main()
{
cin>>n>>r;
for(int i=0;i<n;i++)
{
cin>>a[i];
ans+=a[i];
}
sort(a,a+n);
for(int i=0;i<r;i++) q.push(a[i]); //优先队列中将r个水龙头先进行使用
for(int i=r;i<n;i++)
{
auto t=q.top(); q.pop();
ans+=t;
t+=a[i]; //将该水龙头的时间拿出来,加上当前使用时间,再压入优先队列
q.push(t);
}
cout<<ans;
return 0;
}