题目描述
给定 \(n\) 个数和 \(a,b\) 每次可以选择一段区间 \(+a,-a,+b ,或 -b\),问最少操作几次能把它们都变成 \(0\)。如果无解请输出 \(-1\)。
样例输入
5 2 3
1 2 1 1 -1
5
分析
对于区间修改是很麻烦的,为了简化复杂度,这里可以将数组转化为差分数组以降低难度,对于每一个数,我们实际上都可以找
出一个方程 \(0+ax+by=c\) 这里的 \(c\) 实际上就是原序列数,看着是不是很眼熟,没错,就是扩展欧几里得定理,这里的\(x,y\)
指的是对 \(a,b\) 进行加或减的操作和,因为一次对一个数只有一次操作 \(x\) , \(y\) 是对其他数操作时的影响,所以一次操作被算了两
边,所以最后答案实际上是 \(\frac{x+y}{2}\) ,这里要先处理出方程等于 \(gcd(a,b)\) 的两特解,即为
-
1 \(x\)最小正整数解,\(y\) 最大负整数解
-
2 \(x\)最大负整数解,\(y\) 最小正整数解
这里是因为要保证代价最小,接着根据裴蜀定理,让序列里的数膜上 \(gcd(a,b)\) 判断是否有解,然后我们要不断去找\(x,y\)的最小
加和最小解,因为\(x,y\) 之间具有方程关系,所以只需要考虑 \(x\) 的操作,再进行判断就可以了,这里可以用一个小根堆去维护,
每次取出最小代价操作,这里需要注意一个点,因为操作 \(a,b\) 时有加有减,所以\(x,y\) 可能出现负数,在这里先假设对 \(x\) 的
操作更多且为正,然后根据通解公式$$x=x_0+k*\frac{b}{gcd(a,b)}$$,
\[y=y_0+k*\frac{a}{gcd(a,b)} \]每次让取出的 \(x\) 减去 \(\frac{b}{gcd(a,b)}\) ,对应的 \(y\) 加上 \(\frac{a}{gcd(a,b)}\),不断更新即可,这里可以提前求一下 \(x\) 操作数的和,最多更新次数就是
把这个和变为 \(0\) ,因为已经保证了 \(cnt_x\) \(>\) \(cnt_y\) ,所以对于所有的 \(y\) 一定进行更新了,最后把所有操作的 \(x,y\) 加起来再除二即
为答案
solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=(1<<17)+10;
long long n,m,sum[maxn],a,b,X[maxn],Y[maxn];
priority_queue <pair<int,int> >q;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int res=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-y*(a/b);
return res;
}
bool pd(int x,int y,int xx,int yy)
{
return abs(x)+abs(y)<abs(xx)+abs(yy);
}
signed main()
{
scanf("%lld%lld%lld",&n,&a,&b);
for(int i=1;i<=n;i++)
scanf("%lld",&sum[i]);
for(int i=n+1;i>=1;i--)
{
sum[i]=sum[i]-sum[i-1];//差分,要多处理一个数0,对答案无影响
}
int x=0,y=0;
int d=exgcd(a,b,x,y);
a/=d,b/=d;
for(int xx,yy,i=1;i<=n+1;i++)
{
int c=sum[i]/d;
if(sum[i]%d!=0){puts("-1");return 0;}
xx=X[i]=(x*c%b+b)%b;//x最小正解
yy=Y[i]=(c-xx*a)/b;//y最大负解
xx-=b,yy+=a;
if(pd(xx,yy,X[i],Y[i]))X[i]=xx,Y[i]=yy;
yy=(y*c%a+a)%a;//y最小正解
xx=(c-yy*b)/a;//x最小负解
if(pd(xx,yy,X[i],Y[i]))X[i]=xx,Y[i]=yy;
yy-=a,xx+=b;
if(pd(xx,yy,X[i],Y[i]))X[i]=xx,Y[i]=yy;
}
int temp=0;
for(int i=1;i<=n+1;i++) temp+=X[i];
temp/=b;
if(temp<0)temp=-temp,swap(a,b),swap(X,Y);//保证X为正
for(int i=1;i<=n+1;i++) q.push(make_pair(-(abs(X[i]-b)+abs(Y[i]+a)-abs(X[i])-abs(Y[i])),i));
while(temp--)
{
int u=q.top().second;
q.pop();
X[u]-=b,Y[u]+=a;
q.push(make_pair(-(abs(X[u]-b)+abs(Y[u]+a)-abs(X[u])-abs(Y[u])),u));
}
int ans=0;
for(int i=1;i<=n+1;i++)ans+=abs(X[i])+abs(Y[i]);
printf("%lld",ans>>1);
return 0;
}
标签:frac,WYR,Leveling,int,最小,return,操作,洛谷,gcd
From: https://www.cnblogs.com/oceansofstars/p/18108817