题目描述
对于给定的一个长度为N的正整数数列 A,现要将其分成 M(M≤N)段,并要求每段连续,且每段和的最大值最小。
关于最大值最小:
例如一数列 4 2 4 5 1 要分成 3 段。
将其如下分段:
[4 2][4 5][1]
第 1 段和为 6,第 2 段和为 9,第 3 段和为 1,和最大值为 9。
将其如下分段:
[4][2 4][5 1]
第 1 段和为 4,第 2 段和为 6,第 3 段和为 6,和最大值为 6。
并且无论如何分段,最大值不会小于 6。
所以可以得到要将数列 4 2 4 5 1 要分成 3 段,每段和的最大值最小为 6。
输入格式
第 1 行包含两个正整数 N,M。
第 2 行包含 N 个空格隔开的非负整数 Ai,含义如题目所述。
输出格式
一个正整数,即每段和最大值最小为多少。
输入输出样例
输入 #1
5 3
4 2 4 5 1
输出 #1
6
说明/提示
对于 20% 的数据,N≤10。
对于 40% 的数据,N≤1000。
对于 100% 的数据,1≤N≤10^5,M≤N,Ai<10^8, 答案不超过 10^9。
思路
本题采用二分,贪心以及前缀和的思想,首先我们肯定得对答案进行二分处理,在判定中,我们
对数组求部分前缀和,记录所有不超过mid前缀和的个数如果大于等于m则说明取小了,否则取大了,最后在临近点找到答案
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N];
bool check(int x){
int sum=0,num=0;
for(int i=1;i<=n;i++){
if(sum+a[i]<=x) sum+=a[i];//控制sum<=x;
else sum=a[i],num++;//否则sum=a[i],开始新的前缀和,并且数目加一
}
return num>=m;//判断符合要求的前缀和数目和m的关系
}
int main(){
cin>>n>>m;
int l=0,r=0;//部分和最小肯定不小于元素中的最大值,而最大值不大于所有元素的总和,便确定了l和r
for(int i=1;i<=n;i++){
cin>>a[i];
l=max(l,a[i]);
r+=a[i];
}
while(l<r){//二分答案
int mid=(l+r)/2;
if(check(mid)) l=mid+1;
else r=mid;
}
cout<<l;
}