1830E
CF1830E Bully Sort
我永远喜欢数据结构。 洛谷 CF 对于一个排列 \(P_1\sim P_n\),定义 \(f(P)\) 为重复执行以下操作直至将其升序排序的操作次数: 找到一个位置 \(i\),使得其是满足 \(P_i\ne i\) 的位置中 \(P_i\) 最大的那个位置。 找到一个位置 \(j\),使得其是满足 ......
【题解】CF1830E Bully Sort
考虑一次交换,我们发现,被选出来的 \([i,j]\) 的区间里 \(p_i\) 一定是最大的,\(p_j\) 一定是最小的。 然后我们会发现,我们原序列的逆序对数量会减少 \(2(j-i) - 1\),而 \(\sum|p_i-i|\) 会减少 \(2(j-i)\) 那么答案就是原序列的两部分相减 ......
[CF1830E] Bully Sort
## 题目描述 On a permutation $ p $ of length $ n $ , we define a bully swap as follows: - Let $ i $ be the index of the largest element $ p_i $ such that ......
Codeforces 1830E - Bully Sort
这种题肯定首先要**寻找不变量**。 显然后面排好序的后缀不会被改变。因此从整体上来看我们的流程肯定是,如果当前 $p_n=n$,就令 $n$ 减一,否则你一步换的 $i$ 肯定满足 $p_i=n$。而显然 $\min\limits_{j=i}^np_j\le i$,因此我们考察 $\sum|i-p ......