《算法竞赛》---二分

整数二分经典模型

1.最大值最小化(最大值尽量小)

序列划分-----p48

#include<bits/stdc++.h>
using namespace std;
int n,k;
//long long sum;
int a[1000000];
bool check(int x)
{
    long long res=0,cnt=0;
   res=a[1];
   for(int i=2;i<=n;i++)
   {
       if(res+a[i]<=x)res+=a[i];//注意当最后加入一个元素满足条件时不会再加上一个cnt,要人工特判一下最后面加入
       else 
       res=a[i],cnt++;
       if(res==x&&i==n)cnt++;
   }
   if(cnt>k)return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    cin>>n>>k;
    int r=0,l=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        l=max(a[i],l);
        r+=a[i];
    }
     //cout<<l<<' '<<r<<endl;
    while(l<r)
    {
       // sum=r;
        int mid=(l+r)>>1;
        if(check(mid))l=mid+1;
        else r=mid;
         //  cout<<l<<' '<<r<<' '<<mid<<endl;
    }
    cout<<l;
    return 0;
}