A. Desorting

https://codeforces.com/problemset/problem/1853/A

problem

用操作：\([1,i]++,[i+1,n]--\)，使得数组不单调不降，求最小操作次数。\(n\leq 10^5\)。

solution

操作等同于在差分数组上选出 \(i\)，做 \(c_1:=c_1+1,c_i:=c_i-2\)；又因为除了无用的 \(c_1\) 外，只要 \(c_{[2,n]}\) 中有一个负数，那么对应的原数组就会出现 \(a_{i-1}>a_i\) 的题设。那么先做差分，找到 \(c_{[2,n]}\) 中的最小值，如果已经无序就是 \(0\)，否则是 \(x/2+1\)。

B. Fibonaccharsis

https://codeforces.com/problemset/problem/1853/B
等会

C. Ntarsis' Set

https://codeforces.com/problemset/problem/1852/A

problem

集合 \(S=N^{+}\) 初始时。重复 \(k\) 次，每次都同时删除 \(a_1,a_2,\cdots,a_n\) 小的元素。求操作后 \(S\) 中最小数。\(n,k\leq 10^5\)。

solution

可以考虑原集合的前 \(m\) 个数，每一天，这 \(m\) 个数中的某一些会被删除。因为我们规定这 \(m\) 个数是前 \(m\) 个数，所以删除就是删这 \(m\) 个数的 \(a_1,a_2,\cdots,a_n\) -th。可以二分找出多少个数被删除，也就是记 \(x=\sum_{i}[a_i\leq m]\)，然后 \(m:=m-x\)，继续下一天。如果最终还剩下数字，说明 \(m\geq ans\)；如果删空了，\(m<ans\)。那么二分答案即可。\(O(n\log^2n)\)。

D. Imbalanced Arrays

https://codeforces.com/problemset/problem/1852/B

problem

solution

首先变形 \(b_i+b_j>0\Rightarrow b_j>-b_i\)。当 \(b_i\) 越大，\(-b_i\) 越小，找到的 \(a_i\) 越大。对着 \(a_i\) 排序就能确定 \(b_i\) 的大小关系。

对于符号，如果记 \(a_i\) 排序后 \(a_i\) 最小值的下标为 \(p_1\)，最大值为 \(p_n\)。

对于 \(a_{p_n}\)，如果 \(a_{p_n}=n\)，说明 \(b_{p_n}\) 的相反数小于其它所有数，不妨给它值 \(n\)；
对于 \(a_{p_1}\)，如果 \(a_{p_1}=0\)，说明 \(b_{p_1}\) 的相反数比其他值都大，因为它的值最小，所以它一定是 \(-n\) 了。
按照这样的思路，我们双指针，按照 \(x:n\to 1\) 的顺序，维护 \(l,r\)，每次确定一个 \(b_{p_l}\) 或者 \(b_{p_r}\) 的值为 \(\pm x\)。
我们坚信如果这样的算法无法得出解，则原问题无解。

E. Ina of the Mountain

https://codeforces.com/problemset/problem/1852/C

problem

给出长为 \(n\) 的数组 \(a\)。构造尽量少的区间减操作，使得操作完后，所有 \(a_i\equiv 0\pmod k\)。\(n\leq 10^5,k\leq 10^9\)。

solution

这个问题相当于积木大赛，但是输入的值是对 \(k\) 取模的，我们要最小化答案；在某些情况下，给某个点加 \(k\) 会影响答案（如样例二）。回忆积木大赛的结论，是所有正的差分值之和。考虑从左到右去加入数字使得差分总和最小。我们发现其实使得尽可能多的 \(c_i\) 为负是最优的，但是我们不能对数字减 \(k\)，不能强行减到负数使得它的差分全为负。

考虑一种贪心：

我从左往右加入 \(a_i\)，先把 \(a_i\) 加上和 \(a_{i-1}\) 一样个数的 \(k\)，使得它们持平。
如果 \(a_{i-1}>a_i\) 我就不管。
如果 \(a_{i-1}<a_i\)，我们也许可以使得 \(a_{i-1}\) 额外多加一个 \(k\)，但这样会影响更前面的答案，我们希望找到前面一个点，使得这一段全部加 \(k\)，影响集中到那个点上。

对于最后一种情况，解决的方案是反悔贪心。维护一个决策集合，每个决策表示我可以花 \(x\) 的代价，使得 \(i-1\) 到前面的某一个点 \(j\) 全部加 \(k\)，这个 \(x\) 的代价就是原来 \(a_j\) 因为 \(<a_{j-1}\) 不计算的差分，现在算上 \(a_j+k-a_{j-1}\)。重新设计贪心算法：

如果 \(a_{i-1}>a_i\)，答案不用加，决策集合里面放入 \(a_i+k-a_{i-1}\)。
如果 \(a_{i-1}<a_i\)，将我直接将答案加 \(a_i-a_{i-1}\) 和取前面一个决策的两种方案作比较，选一个最小的加入答案。对于后者，还需要在决策集合里面放入 \(a_i+k-a_{i-1}\)，表示我以后可能还要反悔，可能又不加这个 \(k\) 了，给 \(a_i\) 加回去打平成原来的样子。

那么这个反悔贪心是对的。决策集合需要插入，查询 \(\min\)，删除 \(\min\)，一个堆即可。