分数规划.pdfadfdafsaff
需积分: 0 68 浏览量
2024-01-22
20:55:09
上传
评论
收藏 613KB PDF 举报
分数规划
前置知识：二分答案
CF1486D - Max Median
题目大意：给定一个长度为 的序列 ，求所有长度 的连续子区间中，中位数的最大值。定义中位
数是一个长度为 的序列升序排序后的第 位的值。
数据范围： ，
样例输入：
样例输出：
题解：显然答案具有单调性，因此可以使用二分答案。如何判断一段区间的中位数能否达到某个值？
发现如果区间 内存在一个值 ，当 的数的个数 严格超过 的数时，中位数至少是 。
例：判断序列 的中位数能否达到 。
序列中有 个数不小于 ，有 个数小于 ，因此该序列的中位数不小于 。
而上述过程等同于在序列 中判断区间和能否 。
例：判断序列 中的所有长度 的子区间中，中位数能否达到 。
上述问题等同为判断序列 是否有长度 的子区间和 。
维护前缀和，枚举右端点找长度 的最小前缀， 维护最小前缀，时间复杂度 。
常数优化：答案一定是某个 ，总时间复杂度 .
5 3
1 2 3 2 1
1
2
21
资源评论
