牛客小白月赛111F题解
题目链接
知识点：扩展欧几里得算法，不定方程
因为觉得官方的题解写的不明所以，所以写了这篇题解。
不妨设最终每个数的值为 ，操作数为
，数组的和为
，数组中的最大值为
，最小值为
，
。则有
。
接下来，先用扩展欧几里得求一下这个方程的解，如果无解直接输出 -1。这里还要特判一下 的情况，这种情况下，除非每个数相同，否则都是 -1。现在我们求得了一组解
，要怎么求最小的
呢？
首先，如果 ，则考虑增大
的同时减小
。具体地，令
为最大的非负整数满足
，则使
，
。否则，
不需要减小。
接着，因为每次操作不能将一个 减很多次，则
；因为不能执行加操作，所以
。上面那组不定方程的整数解可以表示为
，带入到这两个不等式中，可以得到两个与
有关的不等式，分别是
和
。解一下就可以得到
的下界，注意向上取整的问题。然后，我们就可以愉快地得到
的最小值了。
代码如下：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
int n, k;
ll sum, mx, mn;
inline void chkmx(ll &x, ll y){
x = x>y?x:y;
}
inline void chkmn(ll &x, ll y){
x = x<y?x:y;
}
int ex_euclid(int a, int b, ll c, ll &x, ll &y){
if(b == 0){
x=c/a, y=0;
if(c%a != 0) return -1;
return a;
}
int g;
ll xx, yy;
g = ex_euclid(b,a%b,c,xx,yy);
x=yy, y=xx-a/b*yy;
return g;
}
int main(){
scanf("%d%d", &n, &k);
int g, a, b;
ll x, y, t=0;
mn = 1e9+1;
for(int i=1; i<=n; ++i){//因为只有最大值、最小值和总和有用，所以不需要存下整个数组
scanf("%lld", &x);
sum += x;
chkmx(mx,x); chkmn(mn,x);
}
if(mx == mn){
printf("0\n"); return 0;
}else if(n == k){
printf("-1\n"); return 0;
}
g = ex_euclid(n,k,sum,x,y);
if(g == -1){//裴蜀定理，判断是否有解
printf("-1\n"); return 0;
}
a=n/g, b=k/g;
if(x < mn){//确保最开始的时候y足够小
t = (mn-x)/b;
x+=b*t, y-=a*t;
t = 0;
}
if(y < 0)//y>=0
chkmx(t, (-y-1)/a+1);
if(x > mn)//最终得到的数x0应该不大于最小值mn
chkmx(t, (x-mn-1)/b+1);
if(mx > x+y)//对最大值减一的次数不超过y次
chkmx(t, (mx-x-y-1)/(a-b)+1);
y += a*t;
printf("%lld\n", y);
return 0;
}/*
5 4
1 2 3 5 5
output:9
7 6
2 2 3 4 5 6 8
output:26
*/
