题目链接：https://codeforces.com/contest/1369/problem/C
将 $n$ 个数分给 $k$ 个人，每个人分 $w_i$ 个数（$\sum_{i = 1}^{k}w_i = n$），每个人的快乐值为分到数的最小值和最大值之和，计算所有人快乐值之和的最大值。
将 $n$ 个数从小到大排序后从两边加起，利用较大的 $w_i$ 跳过尽可能多的较小值。
#include <bits/stdc++.h> using ll = long long; using namespace std; void solve() { int n, k; cin >> n >> k; int a[n] = {}; for (int i = 0; i < n; i++) cin >> a[i]; int w[k] = {}; for (int i = 0; i < k; i++) cin >> w[i]; sort(a, a + n); sort(w, w + k, greater<int>()); ll ans = 0; int l = 0, r = n - k; for (int i = 0; i < k; i++) { if (w[i] == 1) { ans += a[r] + a[r]; ++r; } else { ans += a[l++] + a[r++]; l += w[i] - 2; //跳过的较小值 } } cout << ans << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
Codeforces Round #652 (Div. 2) C. RationalLee（贪心）
原文：https://www.cnblogs.com/Kanoon/p/13189252.html