定义 \(median\) 是一个非降序数组中第 \(\lceil \frac{n}{2} \rceil\) 的数。数组从 \(1\) 开始标号。
给两个数 \(n\) 和 \(k\) ，并给出一个长为 \(nk\) 的数组 \(a\) 。
需要分出为 \(k\) 个大小为 \(n\) 的数组，每个元素需要被严格分入一个数组中。
需要让 \(k\) 个数组的中位数之和最大。询问最大值是多少。
定理：一个数组 \(a\) 中抽出 \(n\) 个数，最大的 \(\lfloor \frac{n}{2} \rfloor\) 不可能为这 \(n\) 个数的中位数。
当需要从大数组 \(a\) 中分出一个大小为 \(n\) 的小数组时，显然 \(a\) 中最大的 \(\lfloor \frac{n}{2} \rfloor\) 个元素不可能是中位数，于是可以让第 \(\lfloor \frac{n}{2} \rfloor - 1\) 大的元素作为当前的中位数。然后从 \(a\) 中抽去最大的 \(\lfloor \frac{n}{2} \rfloor + 1\) 个数，再抽去最小的 \(n - (\lfloor \frac{n}{2} \rfloor + 1)\) 个最小数即可。
上述过程可使当前选出的大小为 \(n\) 的数组中位数最大。
容易证明可以根据上述算法贪心：
- \(a\) 最大的 \(\lfloor \frac{n}{2} \rfloor\) 个数不可能为任何一个大小为 \(n\) 的数组的中位数。
- 抽取最小的 \(n - (\lfloor \frac{n}{2} \rfloor + 1)\) 不会使任何一个数组的中位数更小。
- 第 \(\lfloor \frac{n}{2} \rfloor - 1\) 大的数不会影响后面的中位数。
得证当前的贪心不会对后面的最优化造成影响。于是全局可以贪心。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
int n, k; std::cin >> n >> k;
std::vector<int> a(n * k + 1);
for (int i = 1; i <= n * k; i++) std::cin >> a[i];
std::sort(a.begin() + 1, a.end());
int x = n / 2, r = n * k, l = 1;
ll ans = 0;
while (r - l + 1 >= n) {
ans += a[r - x];
r -= x + 1;
l += n - (x + 1);
}
std::cout << ans << "\n";
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}