蓝桥杯 adv148 排队打水问题

蓝桥杯 adv148 排队打水问题

问题描述

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

输入格式

第一行n,r (n<=500,r<=75)

第二行为n个人打水所用的时间Ti (Ti<=100);

输出格式

最少的花费时间

样例输入

1
2
3 2
1 2 3

样例输出

7

参考解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
int n, r, t[501] = { 0 }, sum = 0 ;
cin >> n >> r;

for (int i = 0; i < n; ++i) {
cin >> t[i];
sum += t[i];
}

sort(t, t+n);
int q = n / r;
int res = n % r;

for (int i = 0; i < r; ++i) {
int tmp = q;
if (res) {
for (int j = 0; j <= q; ++j)
sum += t[j * r + i] * (tmp--);
--res;
} else {
for (int j = 0; j < q; ++j)
sum += t[j * r + i] * (--tmp);
}
}
cout << sum << endl;
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×