数组元素增减1操作下的最大数组美观度求解

问题描述 #

给定大小为N的数组A，你可以进行最多K次操作，每次操作可将数组中的任意一个元素加1或减1。数组的美观度定义为数组中出现频率最高的元素的频次。请计算经过K次操作后能达到的最大美观度。

函数参数与返回值 #

函数接收3个参数：

• N：数组nums的大小
• K：允许的操作次数（整数）
• nums：输入的数组元素
  返回值：经过操作后能达到的最大美观度

自定义测试输入格式 #

• 第一行输入T，表示测试用例数量
• 每个测试用例：
  1. 第一行输入N，表示数组大小
  2. 第二行输入整数K
  3. 第三行输入N个空格分隔的数组元素

约束条件 #

• 1 < T < 10
• 1 < N < 1e5
• 0 < K < 1e18
• -1e9 < Ai < 1e9

解法思路 #

你的初始思路是正确的，核心是排序+前缀和+滑动窗口/二分答案，具体步骤如下：

1. 排序数组：将数组从小到大排序。排序后只需考虑连续子数组——非连续元素调整为同一值的代价必然高于连续子数组，连续子数组元素更集中，调整代价更小。
2. 前缀和预处理：计算前缀和数组，用于快速计算任意区间内元素的总和，进而快速求出将该区间内所有元素调整为某个值的最小操作代价。
3. 滑动窗口/二分答案找最大可行窗口：
   • 滑动窗口（双指针）：用右指针遍历每个位置作为窗口右端点，左指针维护最小左边界，确保将当前窗口内元素调整为右端点元素或中位数的操作代价不超过K，记录过程中最大的窗口长度。
   • 二分答案：二分枚举可能的美观度m（范围1到N），检查是否存在长度为m的连续子数组，将其调整为同一值的最小代价不超过K。若存在则尝试更大的m，否则尝试更小的m。

关键计算细节 #

假设排序后的数组为a[0..n-1]，前缀和数组为s（其中s[0]=0，s[i] = a[0]+a[1]+...+a[i-1]）：

• 若将区间[l, r]（长度len = r-l+1）的元素调整为a[r]，代价为：a[r] * len - (s[r+1] - s[l])
• 若调整为区间中位数a[mid]（mid = l + len//2），最小代价为：a[mid]*(mid-l) - (s[mid] - s[l]) + (s[r+1]-s[mid+1]) - a[mid]*(r-mid)

复杂度分析 #

• 排序时间复杂度：O(N log N)
• 前缀和预处理：O(N)
• 滑动窗口/二分答案：O(N)或O(N log N)
  整体复杂度为O(N log N)，完全适配N<1e5的约束。

内容的提问来源于stack exchange，提问作者vishal akula