第 376 场力扣周赛

使数组成为等数数组的最小代价

题目

输入长度为 \(n\) 的整数数组 \(a\)，输出执行任意次操作后使得数组中的数全部相等并且是回文数的最小代价（要求该回文数小于 \(10^{9}\)）。每次操作可以将数组中的某个数（假设为 \(a_{i}\)）修改为任意正整数（假设为 \(x\)），对应的代价为 \(|a_{i}-x|\)。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq10^{9}\)。

思路

如果没有限制是回文数，那么将数组排序之后按如下方式修改，代价是最小的（假设有序数组中的元素为 \(a_{0},a_{1},\dots,a_{n-1}\)）：

• 当 \(n\) 为奇数时，将所有数修改为中位数 \(a_{\lfloor\frac{n}{2}\rfloor}\)。
• 当 \(n\) 为偶数时，将所有数修改为区间 \([a_{\lfloor\frac{n-1}{2}\rfloor},a_{\lfloor\frac{n}{2}\rfloor}]\) 内的某个数。

首先使用反证法证明，最小代价可以通过将所有数修改为数组中的某个数取到。

• 假设将所有数修改为 \(x\)，\(x\) 在区间 \((a_{i},a_{i+1})\) 范围内，其中 \(a_{i}\) 和 \(a_{i+1}\) 表示数组中相邻的两个数。此时 \(x\) 左边有 \(i+1\) 个元素，右边有 \(n-i\) 个元素。将 \(x\) 修改为 \(a_{i+1}\) 会使代价增加 \((i+1)\times (a_{i+1}-x)\)，并且使代价减少 \((n-i)\times(a_{i+1}-x)\)。将 \(x\) 修改为 \(a_{i}\) 会使代价减少 \((i+1)\times (x-a_{i})\)，并且使代价增加 \((n-i)\times(x-a_{i})\)。
• 当 \(i+1<n-i\) 时，将 \(x\) 修改为 \(a_{i+1}\) 会使代价减少；当 \(i+1>n-i\) 时，将 \(x\) 修改为 \(a_{i}\) 会使代价减少；当 \(i+1=n-i\) 时，将 \(x\) 修改为 \(a_{i}\) 或者 \(a_{i+1}\) 代价不变。
• 特别的，\(x\) 在区间 \([1,a_{0})\) 或者 \((a_{n-1},+\infty]\) 范围内时，同理。

然后再使用反证法证明上述结论：

• 假设将数组中的数都修改为 \(a_{i}\) 时，代价最小，\(a_{i}\) 不满足上述条件。
• 当 \(n\) 为奇数时，由于 \(a_{i}\) 不是中位数：
  • 当 \(i<\lfloor\frac{n}{2}\rfloor\) 时，有 \(i+1<n-1-i\)，此时 \(i\) 每向中位数移动一位，代价都会减少 \((n-1-i)-(i+1)>0\)。
  • 反之亦然。
• 当 \(n\) 为偶数时，同理。

综上，得出按照上述方式修改代价最少，即 \(x\) 越靠近中位数代价越小。所以，如果需要将所有数修改为某个回文数，那么该回文数一定是最靠近中位数的回文数。PS：还是灵神的证明更简单。

该题有两种方法可以找到距离 \(x\) 的最近回文数：

• 方法一：将 \(x\) 的前半部分作为回文根，对称之后得到回文数 \(y\)。如果 \(y<x\)，则将回文根加一再做对称得到回文数 \(z\)，然后取 \(y\) 和 \(z\) 中距离最近者；如果 \(y>x\)，则将回文根减一再做对称得到回文数 \(z\)，然后取 \(y\) 和 \(z\) 中距离最近者；否则，\(x\) 本身就是回文数。注意，排除大于等于 \(10^{9}\) 的回文数，以及做加减法时可能会遇到回文根为 \(100\dots0\) 或 \(99\dots9\) 的特殊情况，此时做对称会得到错误答案，我们应该直接根据长度构造回文数。（这个代码还挺好看，把所有情况都直接循环枚举，就可以不用写那么多判断语句）
• 方法二：枚举出 \([1,10^{9}]\) 范围内的所有回文数，然后二分找到距离 \(x\) 最近的回文数。

执行操作使频率分数最大

题目

输入长度为 \(n\) 的整数数组 \(a\) 和一个整数 \(k\)，输出经过至多 \(k\) 次操作之后，数组中众数的最大频率。每次操作可以选择数组中的某个数 \(a_{i}\)，将其增加或者减少 \(1\)。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq a_{i}\leq 10^{9}\)，\(0\leq k\leq 10^{14}\)。

思路

排序 + 前缀和 + 滑动窗口。要使众数尽可能多，可以首先对数组排序，假设最终众数有 \(x\) 个，那么这 \(x\) 个数一定是在某个子数组中。使用滑动窗口，将尽可能多的数包含在窗口内，同时满足操作次数小于等于 \(k\)，如果大于 \(k\) 则将左端点右移。类似上一题，将窗口内的所有数都修改为窗口的中位数，所需的操作次数最少。窗口的操作次数可以使用前缀和 \(O(1)\) 的计算出来，假设窗口的左右端点的下标分别为 \(i\) 和 \(j\)，中位数的下标为 \(k\)，则窗口的操作次数为：\((a_{k}\times (k-i)-(s[k]-s[i]))+((s[j+1]-s[k+1])-a_{k}\times (j-k))\)。