E-Game_2020牛客暑期多校训练 第十场 E 前缀和

题目：
There are n columns of blocks standing in a row. The i-th column has ai blocks in the beginning. Each block has size 1\times 1\times 11×1×1. Define (x,y) represent the block at column x and is the y-th block from bottom to top. You can perform one operation:

• Push one block to the left, that means you choose one block which has no block at its right and make it move to the left. Because of the friction, the block above it will also move to the left, and because the blocks cannot intersect, the block at its left will move to the left either. This will cause a chain reaction. After every block moved, if some blocks hang in the air, then it will fall because of gravitation. Note that the blocks at column 1 can’t move to the left, so if a movement will cause a block at column 1 move, you can’t perform this operation.then you can perform this operation as long as l exists. Then for all blocks (i,j) that satisfy l< i\leq xl<i≤x and j\geq yj≥y, it moves to (i-1,j). After that, for blocks (x,y) (y>1) that there are no blocks in (x,y-1), it moves to (x,y-1). Repeat doing it until no blocks satisfy the condition.
• 
  
  
  输入输出：
  
  题意：推箱子，只能往左推，不能推最下面那一层，推完后会产生链式反应左边的都被推，考虑重力下降。
  思路：
  箱子排布麻烦的只可能是左高右低，中间高和右边高直接往左推就完事了，也就是直接一平均，如果能整除分配到每一列，那就整除，如果不行，就+1处理，如果是左边高会麻烦，因为左边不能往右边推，所以我们从左开始判断，用前缀和从左遍历一次加一列，用ans更新最高。
  #include
  #include
  #include
  using namespace std;
  typedef long long ll;
  const int N = 1e5 + 10;
  ll s[N],a[N];
  int n;
  int main()
  {
  int T;
  scanf("%d", &T);
  while (T–)
  {
  cin >> n;
  for (int i = 1; i <= n; i++)cin >> a[i], s[i] = s[i - 1] + a[i];
  ll ans=0;
  for (int i = 1; i <= n; i++)
  { if(s[i]%i==0)ans=max(ans,s[i]/i);
  else ans=max(ans,s[i]/i+1);
  }
  cout << ans << endl;
  }
  return 0;
  }