Equalizer

Array Equalizer 题面描述 Jeevan 有两个长度为 \(n\) 的数组：\(a\) 和 \(b\)。他有以下两种操作： 选择一个 \(k\)（\(1 \le k \le n\)），对所有满足 \(1 \leq i \leq n\) 并且 \(1 \le i \times k \le ......

题目链接 先不考虑修改操作。 直接模拟题目意思，可以发现最后留下的一定是最小的数字（因为相同的数每次会保留第一个）。我当时是顺着这个思路做的题目，现在想想反过来想好像会让问题变得更简单，即认为每次保留最后一个相同的数字。 那么现在每次留下的就是最后一个数字，显然每次操作会让这个数字加一，只需要考虑一 ......

G. The Great Equalizer 通过分析之后得知，每次询问的答案就是当前数组中的最大值和当下数组排序后相邻元素差值的最大值之和。 接下来考虑如何维护数组。这会想到用一颗二叉平衡搜索树来实现。这样的一颗树在STL里已经用multiset封装好了，直接使用即可。 创建两个辅助函数add(i ......

## 思路 对于一个数组，每次操作会缩短排序后的数组的相邻两个数的差距，所以总共会执行 $k$ 次操作，其中，$k$ 为排序后的数组的相邻两个数的最大差距。 因为每次操作都会对最大数加 $1$，所以答案就是 $\text{数组中的最大数} + \text{排序后的数组的相邻两个数的最大差距}$。 因 ......

G. The Great Equalizer Tema bought an old device with a small screen and a worn-out inscription "The Great Equalizer" on the side. The seller said tha ......