题解归档 - cf2232B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2232B
• 本地来源：problems/cf2232B/idea.md
• 题目链接：https://codeforces.com/contest/2232/problem/B
• 原始标题：cf2232B - Cake Leveling

思路

cf2232B - Cake Leveling

pattern:
prefix invariant / floor average

claim:
For a prefix of length i, level height H is feasible iff every earlier
prefix has total frosting at least H * length.

why:
Sweeping at height H moves only excess to the right. If some first j
positions have total sum less than H*j, they cannot all end at height H.
Conversely, if every prefix has enough total, the sweep can maintain carry
sum_so_far - H*j >= 0 and level each processed position to H.

answer:
For every i, the maximum feasible level is
min_{1<=j<=i} floor((a_1+...+a_j)/j).

implementation:
Maintain prefix sum and the running minimum of sum/i.

check:
brute.cpp binary searches each prefix height and simulates the carry
condition; random tests compare it with solution.cpp.

代码

来源：problems/cf2232B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:40:56
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll a[maxn+5],t,n,i,sum,mn;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        sum=0;
        mn=(ll)1e18;
        for(i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
            mn=min(mn,sum/i);
            cout<<mn<<(i==n?"\n":" ");
        }
    }
    return 0;
}