1 条题解
-
0
【本题解由站长编写】
排队打水最短总时间:把所有人按打水时间从小到大排序,再依次轮流分配到 r 个水龙头上(第 i 个人用 i % r 号龙头)。总时间 = Σ 每个人的「等待 + 自己的打水时间」,用
finish[k]记录第 k 个龙头累计用时,累加finish[k]即可。装水时间短的人先开始能使总等待最短(交换论证:若 t_a > t_b 却 a 在 b 前,交换后总时间更小)。代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int n, r; cin >> n >> r; vector<int> t(n); for (int &x : t) cin >> x; sort(t.begin(), t.end()); vector<long long> finish(r, 0); long long total = 0; for (int i = 0; i < n; i++) { int k = i % r; finish[k] += t[i]; total += finish[k]; } cout << total << endl; return 0; }
- 1
信息
- ID
- 4180
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者