Median
CF1201C - Maximum Median
思路 二分答案。对于一个mid，查询中位数要是为mid的话至少要做多少次操作，最小操作次数就是排序后从中位数开始计算max(0, mid - v[i])的和 ac代码 #include <bits/stdc++.h> using namespace std; using i64 = long lon ......
『LeetCode』4. 寻找两个正序数组的中位数 Median of Two Sorted Arrays
『1』合并两个正序数组 我的想法： 先借鉴归并排序的关键步骤将两个数组合并，然后根据数组长度是奇数还是偶数返回中位数。 实现代码： class Solution { // Using the Key Thinking of Merge Sort // M is the length of nums1 ......
CodeForces 1526F Median Queries
洛谷传送门 CF 传送门 首先，如果我们确定了 \(1, 2\) 或 \(n - 1, n\) 的位置，我们就能求出原排列。因为题目给了 \(p_1 < p_2\)，所以可以不考虑对称性。也就是说我们知道两个位置是 \(1, 2\) 或 \(n - 1, n\) 但不确定究竟是 \(1, 2\) 还 ......
CF1322E - Median Mountain Range - 总结
CF1322E - Median Mountain Range 考虑分别对每个位置求出最后的数字。先枚举出这个数 \(x\)，并将 \(a_i \ge x\) 的数设为 \(1\)，\(a_i < x\) 的数设为 \(0\)，然后做题目中的操作，若为 \(0\)，则最终结果小于 \(x\)，为 \ ......
PAT_A1029 Median
two_pointers；令两个序列的最后都添加一个很大的数作为哨兵节点，可以简化代码，解决数组问题；使用cin、cout会超时。 ......
[口胡记录] AGC020C Median Sum
（[题目传送门](https://www.luogu.com.cn/problem/AT_agc020_c)） 一开始口胡结论，发现假了…… 把所有的子集和放到数轴上，惊奇地发现它们关于 $\dfrac{sum}{2}$ 对称，于是做一遍存在性背包，从 $\dfrac{sum}{2}$ 开始找第一个 ......
Maximum Median 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1201C) 一道二分题。 熟悉的 $n \le 2 \times 10^5$，一眼二分。 在 `check(x)` 函数里，我们需要判断的是在 $k$ 次操作以内是否能将 $x$ 变为中位数。显然的，我们只需要往 ......
CF1360H Binary Median 题解
提供一份好看的题解。 $2^m-n$ 个数的中位数排名是 $\lfloor\dfrac{2^m-n-1}2\rfloor$（从 $0$ 开始）。因为所有元素是连续的，只要数出被删掉的比中位数小的元素数量，那么 $\lfloor\dfrac{2^m-n-1}2\rfloor$ 加上数量就是中位数了。 ......
AGC022 E Median Replace
考虑操作一共可以根据 $0,1$ 个数分成四类： - $(3,0)$，这个一定很优，因此我们可以先把序列消成连续的 $0$ 最多有 $2$ 个。 - $(0,3)$，这个一定没用，完全可以不消留到最后。 - $(1,2)$ 和 $(2,1)$，感受一下，我们发现这两类其实都是等价于消掉一组 $01$ ......
「解题报告」AGC012F Prefix Median
好可怕。 AtCoder 的一贯风格，先找合法序列的充要条件，然后 DP 计数。 首先把数组排序，这个显然。 先找显然的必要条件。首先 $b_i \in [i,2n - i]$，这个比较显然。 然后发现加数很不好考虑，我们考虑倒过来删数。每次删两个数，不难发现中位数只会不变或向左 / 向右移动一位。 ......