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;}