80141 - 2026挑战赛提高组41·45
统计题目(材料题)
分配人员 把n个人分配到3个部分，其中第i个人对第j个部门的满意度为$a_{i,j}$。最终每个部门的人数均不得超过$\frac{n}{2}$ 。求这n个人最大总满意度。
试使用贪心算法补全程序：
|
#include<bits/stdc++.h> using namespace std; struct sat { int index; int val; }; bool cmp(sat g1, sat g2) { return ① ; } int main() { int n, sum = 0; int dep[4][100001]; int cnt[4]; sat dl[4]; cin >> n; ② ; for (int i = 1; i <= n; i++) { for (int j = 1; j <= 3; j++) { cin >> dl[j].val; dl[j].index = ③ ; } sort(dl + 1, dl + 4, cmp); cnt[dl[3].index]++; sum += dl[3].val; dep[dl[3].index][cnt[dl[3].index]] = ④ ; } for (int j = 1; j <= 3; j++) if (cnt[j] > n / 2) { sort(dep[j] + 1, dep[j] + cnt[j] + 1); for ( ⑤ ) sum -= dep[j][i]; } cout << sum; return 0; } |
关注我们
