wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

算法基础

二维偏序

高维前缀和

树上差分

中位数定理

[[ item.c ]]

中位数定理

## 中位数定理
给定一个数组，每次操作加1或者减1，将所有元素变成相同的最小操作次数
**是将所有元素变成中位数**所需要的操作次数

**[双生双宿之错](https://ac.nowcoder.com/acm/contest/95323/E)**
定义一个数组是双生数组，当且仅当数组的大小是偶数，并且元素的种类恰好是`2`种，并且要求这两种元素的出现次数相同
现在给你一个长度是偶数的数组，每次选择一个元素，使其`+1 or -1`，问将其变成双生数组，最少的操作次数

**算法分析**
首先对数组排序，划分成两部分
前半部分变成前半部分的中位数，后半部分也变成后半部分的中位数

如果前半部分和后半部分的中位数相等，那么分两种情况
要么前半部分变成中位数`-1`，要么后半部分变成中位数`+1`，枚举取最优

## 交换相邻元素
在竞赛中，常常有一类问题，给定目标数组，然后一次操作只能交换相邻元素，问要变成目标数组
所需要的最小操作次数

**[C - Alternated](https://atcoder.jp/contests/abc421/tasks/abc421_c)**
给定长度为$$2n$$的串，拥有相同数量的`a, b`，然后要变成`a, b`间隔，一次操作只能交换相邻字符
问变成目标串，需要的最小操作次数

**算法分析**
枚举`A`所有的位置，`A`要么都处于奇数位，要么都处于偶数位
那么将所有的`A`移动到目标位置，所需要的代价，贪心地，有

* 将所有的`A`位置从小到大排序

* 令$$res = \sum\_{j 是偶数/奇数} |pos(i) - j|$$，`i++, j += 2`，枚举奇偶，求最小代价即可

**[D. A and B](https://codeforces.com/contest/2149/problem/D)**
同样，只能交换相邻元素，只不过这里的合法串，变成了
```bash
aaa...bbb...aaa，所有 b 都在中间
bbb...aaa...bbb，所有 a 都在中间
aaaaabbbbb, bbbbaaaa，所有 a, b 都在两头
```

**算法分析**
首先能想到的是，枚举这`4`种情况，暴力求解，但又不能完全暴力

考虑到一开始把所有的`a`都放在最前面，这样需要交换的次数就是$$\sum|pa_i - i|$$
然后枚举，把`a`的最后一部分后缀，**放到序列的末尾**
```bash
for (int i = pa.size()-1, j = n-1; i >= 0; i--, j--) {
	原来的代价是 raw = pa[i] - i;
	现在，res -= raw;
	res += j - pa[i];
	
	chmin(ans, res)
}
```
这样就可以了，同样的方法枚举`b`
从前缀/后缀考虑，有一点好处，$$|pa_i - i|$$，不需要去绝对值，比如前缀一定有$$pa_i \geqslant i$$
如果是前缀，只取`[0...k]`，那么前缀的贡献，一定是`prea[k] - 1LL * (k+1) * k / 2;`
后缀同理
```bash
void solve() {
    for (int k = 0; k < prea.size(); k++) {
        // [0....k] [k+1...|sz|-1
        i64 left = prea[k] - 1LL * (k+1) * k / 2;

i64 k2 = prea.size() - k - 1;

// [n-1, n-2, ..., n-k2]
        i64 right = 0;
        if (k2 > 0) {
            right = 1LL*k2*n - 1LL*(1+k2)*k2 / 2;
            i64 del = prea.back() - prea[k];
            right -= del;
        }
        chmin(ans, left + right);
    }
}
```

> 中位数优化

实际上，假设说我们的目标是把`a`凑在一起，实际上只需要考虑`a`**归位**
因为只有`a, b`两种不同的元素，把`a`归位，意味着`b`也顺利归位了

不妨设`a`归位后，是从`[L, L+1, ..., L+ma-1]`，其中$$ma$$表示`a`的个数
那么归位的代价是
```math
\displaystyle
\sum_{i= 0}^{ma}|pa_i - (L+i)| = \sum_{i = 0}^{ma} |(pa_i - i) - L|
```
令$$ta_i = pa_i - i$$，那么问题转化成选一个$$L$$，最小化$$\sum|ta_i - L|$$
这个结论是很显然的，对$$ta_i$$排序之后，$$L$$取中位数即可

看完文章有啥想法

算法小站

wiki 主题

算法基础

中位数定理

目录