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 <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
#define N 100005
#define inf 0x3f3f3f3f
using 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<n;i++)a[i]=a[i+1]-a[i];
a[n]=tmp-a[n];
ll d=sum/t,ok=1;
for(int i=1;i<=n&&ok;i++){
a[i]-=d;
if(a[i]%n||a[i]>0)ok=0;
}
if(ok)cout<<"YES";
else cout<<"NO";
}
return 0;
}