题解：P16881 [GKS 2022 #D] Image Labeler

题目传送门

思路

这题让我们最大化每组中位数之和，考虑贪心。

1，将最大的 \(M-1\) 个区域各自作为单独类别每个贡献其全部的值。

2，将剩下的 \(N-M+1\) 个区域合并一下取它的中位数。

为什么要这么做呢？

想要最大化中位数之和，关键在于：

单元素类别贡献最大 ： 如果一个类别只有 \(1\) 个区域，中位数就是该区域的参与者个数。

多元素类别中位数偏小 ： 如果一个类别有 \(k\) 个区域（ \(k ≥ 2\) ），中位数是排序后的中间值，一定会小于最大的那个值。

证明：

假设我们有 \(M\) 个类别，为了最大化总和，对于 \(M-1\) 个类别每个放一个区域时贡献最大，那么剩下的就必须放在同一个类别中了，否则就不合法了，并且剩下的中位数是固定的，与分配方式无关。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {int T;cin >> T;for (int t = 1; t <= T; t++) {int N, M;cin >> N >> M;vector<int> A(N);for (int i = 0; i < N; i++) {cin >> A[i];}sort(A.begin(), A.end()); double ans = 0;for (int i = N - M + 1; i < N; i++) {ans += A[i];}int k = N - M + 1;if (k % 2 == 1) {ans += A[k / 2];} else {ans += (A[k / 2 - 1] + A[k / 2]) / 2.0;}printf("Case #%d: %.1f\n", t, ans);}return 0;
}