AtCoder Grand Contest 010 B题

题意

n个盒子，第i个盒子有ai个石头。

重复这个步骤：选一个盒子i，每次从第i+j个盒子中移走j个石头，j从1到n，第n+k个盒子被称为第k个盒子。若某一轮有盒子里石头不够，就停止，且这一轮都不能执行。问能否清空所有盒子。

题解

首先每轮减少的值是\(t=\sum_{i=1}^{i=n}i\)，因此\(\sum_{i=1}^{i=n}a_i\)必须是t的倍数，否则NO。

这个倍数就是操作的轮数，设为k。

计算出差分\(d[i]=a[i]-a[i-1]\)，对于差分来说，每一轮有一个位置是增加了\(1-n\)，其它位置是增加了1。

现在我们倒回去模拟，每一轮给差分最小的加上\(n-1\)，其它位置-1，如果能使所有差分变为0，那么就是YES。

但是直接模拟肯定超时。

可以观察到k轮后每个位置都减去了若干个1和1-n，把k个1提出来，也就是每个位置先减去k，d[i]-k得是n的倍数，而且是负数[修正：或0]，才是YES，否则NO。

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define ll long long#define N 100005#define inf 0x3f3f3f3fusing namespace std;ll sum,a[N],t,tmp,n;int main() {    cin>>n;    for(int i=1;i<=n;i++){        cin>>a[i];        sum+=a[i];        t+=i;    }    if(sum%t)cout<<"NO";    else{        tmp=a[1];        for(int i=1;i
        
         0)ok=0;        }        if(ok)cout<<"YES";        else cout<<"NO";    }    return 0;}