序列划分

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

主要步骤

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