P1182 数列分段 Section II
P1182 数列分段 Section II - 洛谷
题目描述
对于给定的一个长度为 N 的正整数数列 A1∼AN，现要将其分成 M（M≤N）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 4 2 4 5 1 要分成 3 段。
将其如下分段：
[4 2][4 5][1]
第一段和为 6，第 2 段和为 9，第 3 段和为 1，和最大值为 9。
将其如下分段：
[4][2 4][5 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≤105，M≤N，Ai<108，答案不超过 109。
思路：
暴力，利用桶思维，第一个满足条件的就是答案
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,M;
const ll L = 1e5+10;
ll a[L];
bool check(ll x)
{
// cout << x << endl;ll m = x,t = x,cnt = 1;for(ll i = 1 ; i <= N ; i++){if(t < a[i])return false;if(m - a[i] >= 0){m -= a[i];}else{m = x;m -= a[i];cnt++;}}if(cnt == M)return true;elsereturn false;
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> N >> M;for(ll i = 1 ; i <= N ; i++)cin >> a[i];for(ll i = 1 ; i <= 1e7 ; i++){if(check(i)){cout << i;break;}} return 0;} 
思路：
二分优化，如果我们画二分图我们会发现一个现象。
发现这个条件变化很多，是因为当枚举的区域最大和。
1.我们需要注意l的取值，为了杜绝一开始的cnt < M,l可以取值为数字里面的最大值max_num,这样保证了至少有一个桶。
2.我们不需要注意r的取值，因为右半部分只有cnt<M,这个是在理解范围内的。取最大的数据即可。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,M,max_num = -1e9,;
const ll L = 1e5+10;
ll a[L];
bool check(ll mid)
{ll m = mid;ll cnt = 1;for(ll i = 1 ; i <= N ; i++){if(m - a[i] >= 0){m -= a[i];}else{m = mid;m -= a[i];cnt++;}}if(cnt > M )return false;elsereturn true;
}
int main(void)
{cin >> N >> M;for(ll i = 1 ; i <= N ; i++){cin >> a[i];max_num = max(max_num,a[i]);}ll l = max_num - 1, r = 1e9;while(l + 1 != r){ll mid = (l + r)/2;if(check(mid)){r = mid;}else{l = mid;}}cout << r;return 0;} 