网硕互联帮助中心P1182 数列分段 Section II
题目描述
对于给定的一个长度为
N
N
N 的正整数数列
A
1
∼
N
A_{1\\sim N}
A1∼N，现要将其分成
M
M
M（
M
≤
N
M\\leq N
M≤N）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列
4
2
4
5
1
4\\ 2\\ 4\\ 5\\ 1
4 2 4 5 1 要分成
3
3
3 段。
将其如下分段：
[
4
2
]
[
4
5
]
[
1
]
[4\\ 2][4\\ 5][1]
[4 2][4 5][1]
第一段和为
6
6
6，第
2
2
2 段和为
9
9
9，第
3
3
3 段和为
1
1
1，和最大值为
9
9
9。
将其如下分段：
[
4
]
[
2
4
]
[
5
1
]
[4][2\\ 4][5\\ 1]
[4][2 4][5 1]
第一段和为
4
4
4，第
2
2
2 段和为
6
6
6，第
3
3
3 段和为
6
6
6，和最大值为
6
6
6。
并且无论如何分段，最大值不会小于
6
6
6。
所以可以得到要将数列
4
2
4
5
1
4\\ 2\\ 4\\ 5\\ 1
4 2 4 5 1 要分成
3
3
3 段，每段和的最大值最小为
6
6
6。
输入格式
第
1
1
1 行包含两个正整数
N
,
M
N,M
N,M。
第
2
2
2 行包含
N
N
N 个空格隔开的非负整数
A
i
A_i
Ai，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
输入输出样例 #1
输入 #1
5 3
4 2 4 5 1
输出 #1
6
说明/提示
对于
20
%
20\\%
20% 的数据，
N
≤
10
N\\leq 10
N≤10。
对于
40
%
40\\%
40% 的数据，
N
≤
1000
N\\leq 1000
N≤1000。
对于
100
%
100\\%
100% 的数据，
1
≤
N
≤
10
5
1\\leq N\\leq 10^5
1≤N≤105，
M
≤
N
M\\leq N
M≤N，
A
i
<
10
8
A_i < 10^8
Ai<108， 答案不超过
10
9
10^9
109。
解析
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
// 最小化最大值, 一眼二分, 比较复杂的点在于check函数如何去写
int n, m;
vector<int> a;
int l, r, mid, ans;
// 最大段值的上界
bool check(int upperBound){
// 初始化
int minSegCount = 1;
int sum = 0;
for (int i = 0; i < n; i++) {
if (sum + a[i] <= upperBound) {
// 能加就加
sum += a[i];
}
else {
sum = a[i]; // 如果不能加就重开一段
minSegCount++;
}
}
return minSegCount <= m;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
a.resize(n);
for(int i = 0; i < n; i++){
cin >> a[i];
// 这里一定需要对二分左边界进行控制, 太小会导致check结果不符合预期
l = max(a[i], l);
r += a[i];
}
// r = INT_MAX;
while(l <= r){
mid = l + (r – l) / 2;
/*
mid此刻为分治后段的最大值, 需要判断分治使每一段都 <= mid,
最少可以分min段, 如果 min <= m, 说明mid还可以尝试缩小
这是一个很简单的思维, 如果mid太大, min反而会更小, 反之, min会增大
*/
if(check(mid)){
// 如果可以使 min <= m, 说明mid可以尝试缩小
ans = mid;
r = mid – 1;
}
else{
// 如果不行, 就得调大mid的值
l = mid + 1;
}
}
cout << ans;
return 0;
}
评论前必须登录！
注册