最大中位数问题

本文主要是介绍最大中位数问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：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 此题

这篇关于最大中位数问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程