文章目录

序列划分

最大值最小化——找不同的划分方式中，子序列和的最大值尽量小的值

主要步骤

1.可能最小的子序列和的最大值的二分查找

一个序列的子序列，他的最大值可能的区间为——最小情况：序列的单个元素的最大值（即只把一个元素划分为一个子序列），最大情况：序列的所有元素的总和（即把所有元素划分为一个子序列）。
故区间就为 ： [max,sum]；
二分查找的目的，就是为了更快的查找到<mark>在所有子序列划分方案中</mark><mark>最小的</mark>并且<mark>可以满足划分后子序列个数</mark>的<mark>划分方案的子序列</mark>的<mark>最大值</mark>（这里很绕，多去理解一下）。
二分查找的过程：

  1. 先取区间中点元素（即区间的中间大的元素），判断在该最大值下，序列能否正好分为要求的子序列个数，若<=子序列个数，说明这个最大值，过大（或刚刚好）
  • 以序列{2,2,3,4,5,1}为例，要求将序列分为三个子序列，区间为[5,17]，当最大值取11时，可分为{2，2，3，4}，{5，1}这两个子序列，小于三个，原因是最大值取得过大，序列不足以被分为3个子序列
  1. 若>子序列个数，又说明取得最大值过小了（同上面分析）
  2. 当区间变化为了最小值=最大值时，说明已经找到了<mark>在所有子序列划分方案中</mark> <mark>最小的</mark>并且<mark>可以满足划分后子序列个数</mark>的<mark>划分方案的子序列</mark>的<mark>最大值</mark>
  3. 二分查找部分的代码如下： 
int bin_search(int l, int r) {
   
	while (l < r) {
   
		int mid = l + (r - l) / 2;
		if (check(mid) <= m) {
   
			r = mid;
		}
		else {
   
			l = mid + 1;
		}
	}
	return l;
}
  • check()函数，即为返回该最大值下，序列可以划分为的子序列个数,下面的小主题有代码部分
2.查看该最大值下，序列是否可以划分为要求的n个子序列
int check(int x) {
   
	int cut = 1;
	int s = a[1];
	for (int i = 2; i <= n; i++) {
   
		if (s + a[i] <= x) s += a[i];
		else {
    s = a[i]; cut++; }
	}
	return cut;
}

我们还是以序列{2，2，3，4，5，1}为例，当传入的最大值为11时，

在这里插入图片描述
返回的cut值为2，表明只分成了两个子序列，比三个子序列小，说明最大值选择过大，将右区间缩小为11，再次寻找新区间的中间的值。

完整代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
int n, m;
int a[maxn];
int check(int x) {
   
	int cut = 1;
	int s = a[1];
	for (int i = 2; i <= n; i++) {
   
		if (s + a[i] <= x) s += a[i];
		else {
    s = a[i]; cut++; }
	}
	return cut;
}
int bin_search(int l, int r) {
   
	while (l < r) {
   
		int mid = l + (r - l) / 2;
		if (check(mid) <= m) {
   
			r = mid;
		}
		else {
   
			l = mid + 1;
		}
	}
	return l;
}
int main() {
   
	int t;
	ll mx, sum;
	cin >> t;
	while (t--) {
   
		mx = 0, sum = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
   
			cin >> a[i];
			sum += a[i];
			if (mx < a[i])
				mx = a[i];
		}
		int ans = bin_search(mx, sum);

		cout << ans;
	}
	return 0;
}

文章学习来自 链接：link