2505: 【普及/提高-】【P1182】 数列分段 Section II
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
对于给定的一个长度为N的正整数数列 ，现要将其分成 （）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 要分成 段。
将其如下分段：
第一段和为 ，第 段和为 ，第 段和为 ，和最大值为 。
将其如下分段：
第一段和为 ，第 段和为 ，第 段和为 ，和最大值为 。
并且无论如何分段，最大值不会小于 。
所以可以得到要将数列 要分成 段，每段和的最大值最小为 。
输入
第 行包含两个正整数 。
第 行包含 个空格隔开的非负整数 ，含义如题目所述。
输出
一个正整数，即每段和最大值最小为多少。
样例输入 复制
5 3
4 2 4 5 1样例输出 复制
6提示
对于 的数据，。
对于 的数据，。
对于 的数据，，，， 答案不超过 。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
long long sum[100005];
bool P(int x) {
long long tot=0,cnt=1;
for (int i=1;i<=n;i++) {
if (tot+a[i]>x) {
cnt++;
tot=0;
}
tot+=a[i];
}
return cnt<=m;
}
int find(int L,int R) {
int ans=0;
while (L<=R) {
int mid=(L+R)>>1;
if (P(mid)) {
ans=mid;
R=mid-1;
}
else {
L=mid+1;
}
}
return ans;
}
int main(){
scanf("%d %d",&n,&m);
int L=0,R=0;
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
L=max(L,a[i]);
}
R=sum[n];
printf("%d",find(L,R));
return 0;
}