数列分段 Section II

数列分段 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

6

提示

对于 \(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)\)次。

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

  1. 有上下界

  2. 区间有单调性

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

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

最优解一定可行,但可行解不一定最优。我们假设整个序列具有单调性,且一个数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;
}

热门相关:我的治愈系游戏   回眸医笑,冷王的神秘嫡妃   天神诀   半仙   回眸医笑,冷王的神秘嫡妃