题解 | 牛客周赛 Round 9 D.小美的数组操作
小美的数组操作
https://ac.nowcoder.com/acm/contest/63869/D
链接：https://ac.nowcoder.com/acm/contest/63869/D
来源：牛客网
考虑以下几点:
1.众数个数最多是多少？ sum%n==0?n个:n-1个
题目要求优先求众数个数最多的情况，然后再求其最小的操作数。分以下两种情况考虑，
当sum%n==0时,也就是全部的n个数都能通过有限次变换变成平均值sum/n，那么众数最大个数就是n，此时只要求其操作次数即可;
当sum%n!=0时，此时我们需要选出一个数用来平衡其余n-1个数，使得其剩余的和是n-1的整数倍，基于贪心的局部最优策略我们能想到选择其中的最大值或最小值来充当这个角色
2.达到众数最多个数所需要的最少操作次数
对于第一种情况可以直接计算;
对于第二种情况，用v[n]数组存所有的数，M、m分别表示最大值、最小值的下标，sum表示所有元素的总和。
分别考虑去除最大值和最小值之后计算剩余n-1个数全部转换为平均值所需要的次数，以去除最大值为例，去除最大值v[M]之后，由于可能不是整除所以我们考虑其余数k=(sum-v[M])%(n-1)，为了使得剩余n-1个数总和刚好是n-1的整数倍，我们可以选择将总和中余出的k删掉，此时平均值为p=(sum-v[M])/(n-1);或者再补上一个n-1-k,此时平均值为p=(sum-v[M])/(n-1)+1.
3.怎么计算操作的次数？
实际上我们只需要知道平均值是多少就行了，然后遍历一遍v[n]数组，求其中所有大于平均值的数转换为平均数所需要减去数的总和就是我们要的操作次数（同样也可以计算小于平均数的数），代码中定义了函数cal(取大于平均数计算)，该函数的作用就是给定平均值p和要删除的下标idx，计算操作次数
注意：如果是减去k那么这个操作可以由cal的操作一并算出，如果是加上n-1-k那么就要将cal计算的操作次数加上n-1-k。根据你cal函数中选择计算的方式决定，如果是选择大于平均数的数来计算就按上面的规则，如果选择小于平均数的数来计算那么上面的加减情况则反过来
Code
/*
1.众数个数最多是多少？ sum%n==0?n个:n-1个
2.达到最多个数所需要的最少操作次数
3.考虑选择最大值或最小值作为操作点，同时考虑左中位数和右中位数两种
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int v[n];
long long sum = 0;
int m = 0, M = 0;
for (int i = 0; i < n; i++)
{
scanf("%d", v + i);
sum += v[i];
if (v[i] > v[M]) M = i;
if (v[i] < v[m]) m = i;
}
function<long long(int, int)> cal = [&](int p, int idx)
{
long long res = 0;
for (int i = 0; i < n; i++)
{
if (i == idx)
continue;
if (v[i] > p)
res += v[i] - p;
}
return res;
};
long long ans = 0;
if (sum % n == 0)
ans = cal(sum / n, -1);
else
{
long long k = (sum - v[M]) % (n - 1);
ans = cal((sum - v[M]) / (n - 1), M);
ans = min(ans, cal((sum - v[M]) / (n - 1) + 1, M) + n - 1 - k);
k = (sum - v[m]) % (n - 1);
ans = min(ans, cal((sum - v[m]) / (n - 1), m));
ans = min(ans, cal((sum - v[m]) / (n - 1) + 1, m) + n - 1 - k);
}
cout << ans << endl;
return 0;
}
复杂度分析：
时间复杂度：
空间复杂度： 不考虑题目用于存储数据的v[n]数组
