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会超时。 ......
Codeforces Round 684 (Div. 2) B. Sum of Medians
定义 \(median\) 是一个非降序数组中第 \(\lceil \frac{n}{2} \rceil\) 的数。数组从 \(1\) 开始标号。 给两个数 \(n\) 和 \(k\) ,并给出一个长为 \(nk\) 的数组 \(a\) 。 需要分出为 \(k\) 个大小为 \(n\) 的数组,每个 ......
[arc133e]Cyclic Medians
E - Cyclic Medians 看到中位数,就是经典套路:将\(\geq\)中位数的都赋值为\(1\),\(<\)的赋值为\(0\) 那么对于数\(A\),就等于\(\sum_{i=1}^{\infty}[A\geq i]\) 所以我们考虑枚举中位数,然后若其\(\leq A\),那么就对答案 ......
[口胡记录] 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$ ......
「ARC133E」Cyclic Medians 题解
本文网址:https://www.cnblogs.com/zsc985246/p/17513317.html ,转载请注明出处。 ## 传送门 [「ARC133E」Cyclic Medians](https://atcoder.jp/contests/arc133/tasks/arc133_e) # ......
AtCoder Beginner Contest 304 G Max of Medians
[洛谷传送门](https://www.luogu.com.cn/problem/AT_abc304_g "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/abc304/tasks/abc304_g "AtCoder 传送门") 首先显然二分答案, ......
「解题报告」AGC012F Prefix Median
好可怕。 AtCoder 的一贯风格,先找合法序列的充要条件,然后 DP 计数。 首先把数组排序,这个显然。 先找显然的必要条件。首先 $b_i \in [i,2n - i]$,这个比较显然。 然后发现加数很不好考虑,我们考虑倒过来删数。每次删两个数,不难发现中位数只会不变或向左 / 向右移动一位。 ......
AtCoder Regular Contest 133 E Cyclic Medians
[洛谷传送门](https://www.luogu.com.cn/problem/AT_arc133_e "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/arc133/tasks/arc133_e "AtCoder 传送门") 其实是套路题,但是 ......