二分答案 序列划分

1.函数的返回和可行区应该是一样的
2.可行区选择与题目所求相同
右侧：最小化答案（如本题：寻找数字之和最大的段落最小的值）
左侧：最大化答案

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<long long>arr;
bool check(long long x)
{int cc=1;int c=0;//一开始就是一段cc=1for(auto it:arr){c+=it;if(c>x){cc++;c=it;}}return cc<=m;//单调递减，右侧最小化答案
}
long long find(long long l,long long r)
{while(l+1<r)//名不虚传，二分答案最好的板子{long long mid=(l+r)>>1;if(check(mid)) r=mid;else l=mid;}return r;
}
int main()
{int t;cin>>t;while(t--){cin>>n>>m;arr.clear();int tt=n;long long ii;long long mn=0;long long mm=0;//可以优化左侧是最小的数，千万别排序，arr不是升序降序的改变了题目给的，潜在的危险，不然又找不到哪里错了while(tt--){cin>>ii;arr.push_back(ii);mm+=ii;}long long ans=find(mn,mm);cout<<ans<<endl;}
}