2020牛客多校第十场 E. Game

题解：
实际上从左往右先把所有能推到左边的都尽量平分到到这一部分去，即前缀和 s u m sum sum平分到 l , r l,r l,r ，然后将多余的 r r r块分给 r r r个即可。考虑到第 i i i块可能比第 i − 1 i-1 i−1块小，这时候由于取平均值，故不会更新答案，而当 i i i块比 i − 1 i-1 i−1块大，此时可能会更新答案。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
int q[N], n;

int main() 
{
	int T; scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) scanf("%d", &q[i]);
		int ans = 0;
        ll sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += q[i];
            int t = sum / i;
            if(sum % i) ++t;
            ans = max(t, ans);
        }
        printf("%d\n", ans);
    }
	return 0;
}