P1182 数列分段 Section II——题解

解题思路

答案至少是最大单项，至多是全部元素之和，在这个区间二分。检查上限 lim 时从左到右贪心装入当前段；若再加入一个数会超限，就新开一段。该方法得到满足上限所需的最少段数，段数不超过 $M$ 即可行。

复杂度分析

时间复杂度 $O(N\log\sum A_i)$，空间复杂度 $O(N)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,m;cin>>n>>m;vector<long long>a(n);long long lo=0,hi=0;for(auto &x:a){cin>>x;lo=max(lo,x);hi+=x;}
    auto ok=[&](long long lim){int seg=1;long long sum=0;for(long long x:a){if(sum+x>lim){seg++;sum=x;}else sum+=x;}return seg<=m;};
    long long ans=hi;while(lo<=hi){long long mid=(lo+hi)/2;if(ok(mid))ans=mid,hi=mid-1;else lo=mid+1;}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n,m;cin>>n>>m;vectora(n);long long lo=0,hi=0;for(auto &x:a){cin>>x;lo=max(lo,x);hi+=x;} auto ok=[&](long long lim){int seg=1;long long sum=0;for(long long x:a){if(sum+x>lim){seg++;sum=x;}else sum+=x;}return seg<=m;}; long long ans=hi;while(lo<=hi){long long mid=(lo+hi)/2;if(ok(mid))ans=mid,hi=mid-1;else lo=mid+1;} cout<<ans<<'\n';return 0; }