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]$,这个比较显然。 然后发现加数很不好考虑,我们考虑倒过来删数。每次删两个数,不难发现中位数只会不变或向左 / 向右移动一位。 ......