如何上传文件到网站,商场设计规范,网站调用优酷视频去除广告的方法,网页视频怎么下载到电脑桌面一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
D - Med-imize 二、解题报告
1、思路分析
对于n k的情况直接排序就行
对于n k的情况
最终的序列长度一定是 (n - 1) % k 1
这个序列是原数组的一个子序列
对于该序列的第一个元素#xff0…一、题目
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::vectorint 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::vectorint 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::vectorint 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;
}
