点击打开链接
题意:n块box排成一个环(n<=1e5),box有若干个stone(ai<=1e9),操作op:从选第i个box开始,j=1~n,在(i+j)个box中拿j个石头,使用操作时box的石头必须>=拿走的石头 问能否存在有限个操作使得所有box的石头变为0
先看必要条件:每次操作使得总的stone减少n(n+1)/2,stone的总数必须为n(n+1)/2的倍数 假设有解:操作次数k=sum/(n(n+1)/2),设di=a(i+1)-a(i) 每次操作会使得di减小1 i为开头->di增大n-1,k次操作后di为0 则 di-(k-x)+(n-1)x=0 x为i做开头操作的次数 化简得 k-di=nx 充要条件:即对于每个i:k-di>=0&&为n的倍数(算出每个i的x即能求出操作序列) segma(xi)=segma((k-di)/n)必须=k 因为sum of di=0 所有总是segma(xi)总是为k.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; ll a[N],d[N]; int main() { ll n; while(cin>>n) { ll sum=0; for(int i=1;i<=n;i++) { scanf("%I64d",&a[i]); sum+=a[i]; } for(int i=1;i<=n;i++) { if(i==n) d[i]=a[1]-a[n]; else d[i]=a[i+1]-a[i]; } bool flag=true; ll t=n*(n+1)/2; ll k=sum/t; if(sum%t) { puts("NO"); continue; } for(int i=1;i<=n;i++) { if((k-d[i]<0)||(k-d[i])%n) flag=false; } if(flag) puts("YES"); else puts("NO"); } return 0; }
