标签：二分 maxx int mid 答案 check
- P1182 数列分段 Section II
#include<bits/stdc++.h> using namespace std; int n,m; int maxx=0; int a[100005]; //最大值最小化 bool check(int x) { long long sum=a[0]; int cnt=0; for(int i=1;i<n;i++) { if(sum+a[i]<=x) sum+=a[i]; else { cnt++; sum=a[i]; } } return cnt+1<=m; } /* 测试用例：2 2 8 9 */ int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; maxx=max(maxx,a[i]); } //使用二分枚举答案时，首先要确定l和r的初始值 //l不一定每次都是0 //二分枚举答案，判断答案是否可行 int l=maxx;//初始时，l是数组中元素的最大值 int r=1e9; while(r>=l) { int mid=l+(r-l)/2; if(check(mid)) r=mid-1; else l=mid+1; } cout<<l<<endl; return 0; }
标签：二分,
maxx,
int,
mid,
答案,
check
From： https://www.cnblogs.com/FFRcode/p/18335205