P1182 数列分段`Section II`

本文主要是介绍P1182 数列分段`Section II`，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

---

个人思路：

• 显然是二分，但是有几个点要注意.
• 左边界l需要初始化为数列中的最大值，否则就要在judge方法中进行繁琐的判断
• m是分成的段数，实际只能分m-1次
• 洛谷的评测机不会给变量自动赋值，需要手动初始化l,r

---

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1000010,INF=2e9;
int a[MAXN],n,m;
bool judge(int x){int nowTotal=0,rest=m-1;for(int i=1;i<=n;i++){if(nowTotal+a[i]<=x){nowTotal+=a[i];}else{rest--;nowTotal=a[i];}}return rest>=0;
}
int main(){int l,r;l=-2e9,r=2e9;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);l=max(l,a[i]);}while(l<r){int mid=(l+r)>>1;if(judge(mid))r=mid;else l=mid+1;}cout<<l<<endl;return 0;
}

 

这篇关于P1182 数列分段`Section II`的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---