题目描述
有 N 个人排队到 M 个水龙头去打水, 他们装满水桶的时间 T1,T2,...,Tn 为整数且各不相等, 应如何安排他们的打水顺序才能使他们花费的总时间最少?
输入格式
第一行, 两个整数 n 和 m,n 表示人的个数, m 表示水龙头的个数;
第二行, n 个数, 分别表示 n 个人装水的时间;
输出格式
一行, 一个整数, 表示总花费的最少时间.
输入样例
6 2
5 4 6 2 1 7
输出样例
40
题解
我们开一个数组维护 $m$ 个水龙头当前的打水等待时间, 每次选时间最小的打水即可.
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int n, m;
- int a[1005];
- int s[1005];
- int ans;
- int main()
- {
- cin>> n>> m;
- for(register int i = 1; i <= n; ++i)
- {
- cin>> a[i];
- }
- sort(a + 1, a + n + 1);
- s[0] = 214743647;
- int pos;
- for(register int i = 1; i <= n; ++i)
- {
- pos = 0;
- for(register int j = 1; j <= m; ++j)
- {
- if(s[pos]> s[j]) pos = j;
- }
- s[pos] += a[i];
- ans += s[pos];
- }
- cout << ans;
- return 0;
- }
参考程序
来源: http://www.bubuko.com/infodetail-3044451.html