【洛谷 P1182】数列分段 Section II 题解（二分答案+递归）

数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\le N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $42451$ 要分成 $3$ 段。

将其如下分段：

$$[42][45][1]$$

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

$$[4][24][51]$$

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $42451$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

输入格式

第 $1$ 行包含两个正整数 $N,M$。

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

样例 #1

样例输入 #1

5 3
4 2 4 5 1

样例输出 #1

6

提示

对于 $20\%$ 的数据，$N\le 10$。

对于 $40\%$ 的数据，$N\le 1000$。

对于 $100\%$ 的数据，$1\le N\le 10^5$，$M\le N$，$A_i<10^8$， 答案不超过 $10^9$。

思路

函数check用来判断当前的x是否满足条件。在函数check中，会遍历数列a[N]，将当前位置的数加到sum上，并判断sum是否超过x。如果超过x，则创建新区间，将sum重新赋值为当前位置的数，并将cnt加1。最后，返回cnt是否大于m。

首先读入n和m的值，然后读入数列a[N]的值，并初始化l和r的值。因为所有元素都要划入区间内，所以要保证最大的元素也要被划进某一个区间，l初始化为数列a[N]中的最大值。如果把所有元素都划进区间，那么区间的最大值肯定不会超过所有元素的和，r初始化为数列a[N]中所有数的和。

函数partition用于进行二分查找。在partition函数中，首先定义了变量l和r，分别表示当前二分查找的左边界和右边界，初始时l为0，r为数组a的所有元素之和。然后调用check函数判断中间值mid是否满足条件，如果满足，则继续在[mid+1, r]范围内进行二分查找，否则在[l, mid-1]范围内进行二分查找。最后输出结果r+1，即为最终的答案。

注意：check函数中，需要将区间数cnt初始化为1，因为最少有一个区间。

AC代码

#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1e6 + 7;

int n, m;
int a[N];

bool check(int x) {
	int sum = 0;
	int cnt = 1;
	for (int i = 1; i <= n; i++) {
		int tmp = sum + a[i];
		if (tmp > x) {
			// 创建新区间
			sum = a[i];
			cnt++;
		} else {
			sum = tmp;
		}
	}
	// cout << x << " " << cnt << endl;
	return cnt > m;
}

void partition(int l, int r) {
	if (l > r) {
		cout << r + 1 << endl;
		return;
	}
	int mid = (l + r) >> 1;
	if (check(mid)) {
		// 偏小
		partition(mid + 1, r);
	} else {
		// 偏大
		partition(l, mid - 1);
	}
}

int main() {
	int l, r;
	l = 0;
	r = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		l = max(l, a[i]);
		r += a[i];
	}
	partition(l, r);
	return 0;
}