记录编号	361018	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	修整数列	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.410 s
提交时间	2017-01-02 17:27:27	内存使用	2.33 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,a,b,Gcd,c[N],p[N];
ll tx,ty,x[N],y[N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void ex_gcd(ll a,ll b,ll &x,ll &y){
	if (!b){x=1;y=0;return;}
	ex_gcd(b,a%b,x,y);
	ll m=x;
	x=y;y=m-a/b*y;
}
void Min(ll &x,ll &y){//将|x+y|调整到最小，保持ax+by不变 
	ll x1=x,x2=x,y1=y,y2=y;
	ll tmp1=x/b;x1-=tmp1*b;y1+=tmp1*a;
	ll tmp2=y/a;x2+=tmp2*b;y2-=tmp2*a;
	if (abs(x1)+abs(y1)<abs(x)+abs(y)) x=x1,y=y1;
	if (abs(x2)+abs(y2)<abs(x)+abs(y)) x=x2,y=y2;
	if (x1>0) x1-=b,y1+=a;else x1+=b,y1-=a;
	if (y2>0) x2+=b,y2-=a;else x2-=b,y2+=a;
	if (abs(x1)+abs(y1)<abs(x)+abs(y)) x=x1,y=y1;
	if (abs(x2)+abs(y2)<abs(x)+abs(y)) x=x2,y=y2;
}
typedef pair<ll,int> pr;
priority_queue<pr> Q;
void insert(int i){//将对i点的操作方式变换一下的代价为.first 
	Q.push(make_pair(abs(x[i])+abs(y[i])-abs(x[i]-b)-abs(y[i]+a),i));
}
int main()
{
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	scanf("%d%d%d",&n,&a,&b);
	ex_gcd(a,b,tx,ty);
	Gcd=gcd(a,b);a/=Gcd;b/=Gcd;
	for (int i=1;i<=n;i++){
		scanf("%d",&c[i]);
		if (c[i]%Gcd) puts("-1"),exit(0);
		c[i]/=Gcd;
	}
	ll Sx=0,Sy=0;
	n++;
	for (int i=1;i<=n;i++){
		p[i]=c[i]-c[i-1];
		x[i]=-tx*p[i];y[i]=-ty*p[i];
		Min(x[i],y[i]);
		Sx+=x[i];Sy+=y[i];
	}
	if (Sx<0){
		swap(a,b);swap(Sx,Sy);
		for (int i=1;i<=n;i++) swap(x[i],y[i]);
	}
	for (int i=1;i<=n;i++) insert(i);
	//一次区间操作，等价于差分序列上两个单点修改，且和不改变 
	while (Sx){
		int now=Q.top().second;Q.pop();
		Sx-=b;Sy+=a;
		x[now]-=b;y[now]+=a;
		insert(now);
	}
	//一次区间变换等价于在差分序列上两次操作 
	ll ans=0;
	for (int i=1;i<=n;i++) ans+=abs(x[i])+abs(y[i]);
	printf("%lld\n",ans>>1); 
	return 0;
}