5.24 二分答案2
课堂练习
U564349 限时秒杀
题意：。。。。。
单调性分析：什么越大，什么什么就越大。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[10000001],l,r;
// 这个函数是干什么的
bool check(int x){
int sum=0,ans=0; //
for(int i=1;i<=n;i++){
if(sum+a[i]<=x) sum+=a[i];
else{
ans++;
sum=a[i];
}
}
if(sum!=0) return ans+1<=m;
else return ans<=m;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
l=max(l,a[i]);
r+=a[i];
}
l=l-1,r=r+1; // 为什么要初始化为这个
while(l+1<r){
int mid=(l+r)/2;
if(check(mid)) r=mid; // 为什么要r=mid
else l=mid;
}
cout<<r; //为什么要输出r
return 0;
}