数列分段 Section II
题目描述
对于给定的一个长度为N的正整数数列 \(A_{1\sim N}\),现要将其分成 \(M\)(\(M\leq N\))段,并要求每段连续,且每段和的最大值最小。
关于最大值最小:
例如一数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段。
将其如下分段:
第一段和为 \(6\),第 \(2\) 段和为 \(9\),第 \(3\) 段和为 \(1\),和最大值为 \(9\)。
将其如下分段:
第一段和为 \(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)\)次。
我们把这个方法叫做“二分答案”。顾名思义,它用二分的方法枚举答案,并且枚举时判断这个答案是否可行。但是,二分并不是在所有情况下都是可用的,使用二分需要满足两个条件:
-
有上下界
-
区间有单调性
二分答案应该是在一个单调闭区间上进行的。也就是说,二分答案最后得到的答案应该是一个确定值,而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性,那么这个单调性应该体现在哪里呢?
可以这样想,在一个区间上,有很多数,这些数可能是我们这些问题的解,换句话说,这里有很多不合法的解,也有很多合法的解。我们只考虑合法解,并称之为可行解。考虑所有可行解,我们肯定是要从这些可行解中找到一个最好的作为我们的答案, 这个答案我们称之为最优解。
最优解一定可行,但可行解不一定最优。我们假设整个序列具有单调性,且一个数x为可行解,那么一般的,所有的 \(x'(x'<x)\) 都是可行解。并且,如果有一个数y是非法解,那么一般的,所有的 \(y'(y'>y)\) 都是非法解。
那么什么时候适用二分答案呢?注意到题面:使得选手们在比赛过程中的最短跳跃距离尽可能长。如果题目规定了有“最大值最小”或者“最小值最大”的东西,那么这个东西应该就满足二分答案的有界性(显然)和单调性(能看出来)。文章来源:https://www.toymoban.com/news/detail-514551.html
所以(快点)上代码吧。。。文章来源地址https://www.toymoban.com/news/detail-514551.html
#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;
}
到了这里,关于数列分段 Section II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!