最大中位数问题
2021/9/29 23:12:44
本文主要是介绍最大中位数问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:CF1486D Max Median
即给定一个长度为 \(n\) 的序列 \(\{a\}\),求所有长度 \(\geqslant k\) 的子串中,中位数的最大值。
请记住一个套路:二分中位数答案并将原序列按与中位数的大小关系分为两部分。
sol:
在 \(a\) 的值域内二分答案 \(x\),\(check\) 一下答案是否能大于等于 \(x\)。
因为此时我们只关心 \(a_1,a_2,a_3\dots a_n\) 和 \(x\) 的相对大小关系,所以我们可以构造一个序列 \(\{b\}\):
\[b_i=\begin{cases} 1 & a_i\geqslant x \\ -1 & a_i<x \end{cases} \]此时序列 \(\{a\}\) 的中位数 \(\geqslant x\) 当且仅当 \(\exists l\leqslant r-k+1,\sum\limits^r_{i=l}b_i>0\)。
维护一下 \(\{b\}\) 的前缀和和前缀最小值即可 \(O(n\log n)\) AC 此题
这篇关于最大中位数问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现