二分+dp，CF 1993D - Med-imize

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

D - Med-imize

---

二、解题报告

1、思路分析

对于n <= k的情况直接排序就行

对于n > k的情况

最终的序列长度一定是 (n - 1) % k + 1

这个序列是原数组的一个子序列

对于该序列的第一个元素，其下标 mod k 一定为0

为什么呢？

不为0，则第一个元素前面的元素不能删除干净

那么，为了让剩下的元素都能合法的拿进来，两两元素之间的距离应为k的倍数

继而推出，剩余序列在原数组的下标mod k 为[0, k - 1]

那么原数组中的元素要么不能拿进最终序列，要么在最终序列中的位置是确定的

我们记可拿进最终序列的数的集合为S

现在由于要求最终中位数的最大值，我们假设最终中位数为x

我们发现x越大，S中比x大的数目越少，具有单调性，于是就可以二分了

如何check？

利用线性dp，判断长度为(n - 1) % k + 1的最终序列中最多有多少个数 >= x

假如最终结果是cnt，那么只要cnt * 2 > (n - 1) % k + 1，说明可能还能更大，我们就收缩左边界

否则收缩右边界

本题要点：分析出最终序列原数组下标mod k 的特点，以及中位数的单调性

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>
#include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1e-9;void solve() {int n, k;std::cin >> n >> k;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];    }if (n <= k) {std::sort(a.begin(), a.end());std::cout << a[(n - 1) / 2] << '\n';return;}int sz = n % k;if (!sz) sz = k;auto check = [&](int x)-> bool {std::vector<int> f(sz, -inf32);for (int i = 0; i < n; ++ i) {int j = i % k;if (j >= sz) continue;f[j] = std::max(f[j], (j ? f[j - 1] : 0) + (a[i] >= x));}return f.back() * 2 > sz;};std::vector<int> b(a);std::sort(b.begin(), b.end());b.resize(std::unique(b.begin(), b.end()) - b.begin());int lo = 0, hi = b.size();while (hi - lo > 1) {int x = lo + hi >> 1;if (check(b[x]))lo = x;elsehi = x;}std::cout << b[lo] << '\n';
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;std::cin >> t;while (t --)solve();return 0;
}