closefrom

一般看到所谓的最大值最小化或者最小值最大化一般都是用二分答案进行运算。

可能一般你会感觉好像复杂度很大的样子，像这题我刚开始也是以为10^10??复杂度完全不能过

但是二分答案实际上是对你可能求出的值域进行二分，然后得到最优的解法

二分答案的模板很好写，但是最难写的还是所谓的检验函数，一般二分答案就是考察这个！

#include <cstdio>
using namespace std;
int n,m,sum,nm[100005];
bool check(int md){
    int fm=1,sm=0;
    for(int i=1;i<=n;i++){
        sm+=nm[i];
        if(sm>md){
            fm++;
            sm=nm[i];
        }
    }
    if(fm>m)return true;
    else return false;
}
/*
函数check检验当前传进来的数，能分多少段，fm表示分了多少段，
若fm>m,即 用当前传进来的数进行分段，最多可以分到fm段，比数据给出来的m还要大，也就是传进来的md小了，要变大，即 l=mid+1；
*/
int max(int a,int b){return a>b?a:b;}
int main(){
    scanf("%d%d",&n,&m);
    int l;
    for(int i=1;i<=n;i++){scanf("%d",&nm[i]);sum+=nm[i];l=max(l,nm[i]);}
    int r=sum;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
        }else r=mid;
    }
    printf("%d",r);
    return 0;
}