P1182解题报告

GossWandering · 2020-04-29 20:06:49 · 个人记录

关键词：最大值最小

考虑二分，注意细节

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010];
bool check(int x){
    int temp=0,ans=1;
    for(int i=1;i<=n;i++){
        if(a[i]>x) return false;
        if(a[i]+temp<=x) temp+=a[i];
        else {
            ans++;
            temp=a[i];
        }
    }
    return ans<=m;
}
int main(){
    cin>>n>>m;
    int maxx=-0x7f7f7f7f,sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxx=max(maxx,a[i]);
        sum+=a[i];
    }
    int L=maxx,R=sum;
    while(L<R-1){
        int mid=(L+R)/2;
        //cout<<L<<" "<<R<<" "<<mid<<endl;
        if(check(mid)) R=mid;
        else L=mid;
    }
    cout<<R;
    return 0;
}