51nod 1128 正整数分组 V2

二分答案。。因为是单调函数，如果k越大，x就越小。

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef double dl;
using namespace std;

const int N=2e5+7;
const ll M=1e9+7;
const int INF=0x3f3f3f3f;

int n,k;
ll a[N];

struct node 
{
    int l,r;
    int v;
}tr[N*4];

bool check(ll x)
{
    ll sum=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(sum+a[i]<=x)    sum+=a[i];
        else 
        {
            cnt++;
            sum=a[i];
        }
    }
    if(sum) cnt++;
    return cnt<=k;
}

void solve()
{
    scanf("%d%d",&n,&k);
    ll l,r;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),r+=a[i];
    l=0,r=r+1;
    //printf("check:%lld",check(5));
    while(l<r)
    {
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
        //printf("mid:%lld\n",mid);
    }
    printf("%lld",l);
}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    //int T; scanf("%d",&T)
    //for(int i=1;i<=T;i++)
        solve();
}