官方题解

题目大意

有 $n$ 堆石子，每次可以选择一堆将至多 $k$ 个石子移动到相邻的石子堆中，求将所有石子合并到一堆所需要的最少操作次数。

解题思路

如果要将第 $i$ 堆石子合并到第 $i+1$ 堆中，假设第 $i$ 堆有 $x$ 个石子，所需要的操作次数为 $\lceil\frac{x}{k}\rceil$ 。

如果最终所有石子会合并到第 $i$ 堆中，由于中间计算过程中涉及到上去整，所以 $[1,i-1]$ 堆一定是从第 $1$ 堆向右合并的，$[i+1,n]$ 堆一定是从第 $n$ 堆向左合并的。我们可以先预处理合并前缀所需最小操作次数以及合并后缀最小操作次数。

所以我们可以枚举最终合并到哪一堆中，统计合并成一堆所需最小操作次数即可。

参考答案

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;
const ll INF = 1e18+10;

int n,k;
int a[N];
ll pre[N],suf[N];

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        pre[i]=pre[i-1]+(sum+k-1)/k;
    }
    sum=0;
    for(int i=n;i>=1;i--){
        sum+=a[i];
        suf[i]=suf[i+1]+(sum+k-1)/k;
    }

    ll res=INF;
    for(int i=1;i<=n;i++){
        res=min(res,pre[i-1]+suf[i+1]);
    }
    cout<<res<<endl;

    return 0;
}