数列分段 Section II

2023-07-02 15:48 由 Momo·Trace 发表于 #后端开发

数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 \(A_{1\sim N}\)，现要将其分成 \(M\)（\(M\leq 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\) 个空格隔开的非负整数 \(A_i\)，含义如题目所述。

输出格式

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

样例 #1

样例输入 #1

5 3
4 2 4 5 1

样例输出 #1

提示

对于 \(20\%\) 的数据，\(N\leq 10\)。

对于 \(40\%\) 的数据，\(N\leq 1000\)。

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

解析&代码

二分答案

先介绍下二分答案吧

比如我们要从一本英汉词典上查一个单词，如果你从头到尾一页一页的翻着找（并仔细一点），这样找可以保证一定能找到，但是最坏情况你要把整本词典都翻一遍，那就麻烦了（而且很累）。

有什么改进的方法吗？当然有。

我们考虑把这个词典从中间分开，看一下中间那一页的主要单词都是啥，然后去判断我要找的单词应该在左半部分还是右半部分，再去那一部分考虑怎么找就好了。同样的，在另一部分也是要进行划分并且判断的操作。这样一直进行下去，便能很快的找到答案，而且根本不需要翻过整个词典来。

可以证明，如果一页一页的找，最多要找 \(n\) 次，但是用这个方法，最多找\(floor(log2n)\)次。

我们把这个方法叫做“二分答案”。顾名思义，它用二分的方法枚举答案，并且枚举时判断这个答案是否可行。但是，二分并不是在所有情况下都是可用的，使用二分需要满足两个条件:

有上下界
区间有单调性

二分答案应该是在一个单调闭区间上进行的。也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性，那么这个单调性应该体现在哪里呢？

可以这样想，在一个区间上，有很多数，这些数可能是我们这些问题的解，换句话说，这里有很多不合法的解，也有很多合法的解。我们只考虑合法解，并称之为可行解。考虑所有可行解，我们肯定是要从这些可行解中找到一个最好的作为我们的答案，这个答案我们称之为最优解。

最优解一定可行，但可行解不一定最优。我们假设整个序列具有单调性，且一个数x为可行解，那么一般的，所有的 \(x'(x'<x)\) 都是可行解。并且，如果有一个数y是非法解，那么一般的，所有的 \(y'(y'>y)\) 都是非法解。

那么什么时候适用二分答案呢？注意到题面：使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了有“最大值最小”或者“最小值最大”的东西，那么这个东西应该就满足二分答案的有界性（显然）和单调性（能看出来）。

所以（快点）上代码吧。。。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[100010],l,r;
int f(int x)
{
	int ret=0,last=0;
	for(int i=1;i<=n;i++)
	{
		if(last+a[i]<=x)
		{
			last+=a[i];
		}
		else{
			ret++;
			last=a[i];
		} 
	}
	return ret;
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=n;i++)
	{
	 	l=max(l,a[i]);
		r+=a[i];
	}
	while(l<r)
	{
		int mid=(l+r)/2;
		if(f(mid)>=m)
		{
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	cout << l;
	return 0;
}