整数二分经典模型
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;
}