第二题
题目描述
给定一个长度为 N 的序列 A ，要求把该序列分成若干段，在满足“每段中所有数的和”不超过M的前提下，让“每段中所有数的最大值”之和最小。
试计算这个最小值。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数，表示完整的序列A。
输出格式
输出一个整数，表示结果。
如果结果不存在，则输出-1。
数据范围
$0 \le N \le 10^5$,
$0 \le M \le 10^{11}$,
序列A中的数非负，且不超过$10^6$
输入样例：
8 17
2 2 2 8 1 8 2 1
输出样例：
12
解题报告
题意理解
题目让我们随意将一个区间划分,但是要求划分的每一段的和不能超过$M$.
我们可以认为每一段的最大值为这一段的权值.
现在要求一种划分方式,使得所有段的权值和最小.
以下为这道题目的样例解释.
样例分为三段,第一段权值为$2$,第二段权值为$8$,第三段权值为$2$.所以总和为$2+8+2=12$.
算法处理
动态规划
无解判断:如果一个数大于$M$的话,那么必然无解,否则我们一个数一段,可以保证有解.
区间划分问题,和动态规划算法中的区间DP联系紧密,于是这道题目我们不难想到要使用区间DP算法.
一般来说,动态规划算法的状态设置,往往会和题目中的条件以及最后答案有所关联,所以说我们不妨这样设定状态.
我们可以设$F[i]$表示为前$i$个数中任意划分的最小值.
那么既然如此的话,对于状态转移方程,我们也很好设定.
对于$F[i]$而言,我们可以认为将其分成$[1,j]$这个区间和$[j+1,i]$这个部分.
一个是区间,一个是部分.
然后对于$[1,j]$区间,这个区间的花费显然是$F[j]$.
对于后面这个区间,它的花费必然就是$\max{(a[j+1],a[j+2],a[j+3],…,a[i])}$,也就是这个部分的权值.不过这里有一个条件,就是我们$[j+1,i]$这个部分的和必须小于$M$,否则违反题意,而导致无效.
所以我们不难推出这个状态转移方程.
$$
F[i]=\min_{0 \le j < i且\sum_{k=j+1}^i}{F[j]+\max {A_k}}
$$
但是我们发现虽然状态转移方程推出来了,但是时间复杂度却是$O(n^2)$,这显然会超时,我们不得不思考优化方法.
单调队列
动态规划的优化,就是排除无用的决策,对于每一个状态转移方程,显然我们只会取出一个$j$,其他的都是无效点,那么我们当前的问题就是在于,如何快速找到这个最优点$j$
候选答案是一个区间,但是我们只要一个最小值的点.
区间中选一点,这是什么意思?这是单调队列最明显的特征之一.
既然我们现在发现这道题目使用单调队列进行优化,那么我们就要想单调队列里面,生存价值的评估条件是什么?我们需要发掘什么性质&条件?
一个最优点$j$显然是要满足一系列条件的.
- 必须满足[j+1,i]这段区间的和$\le m$.(题意合法性)
- $A_j=\max_{j \le k \le i}{A_k}$ 这句话的意思就是,第$j$个点,是[j+1,i]这个区间的最大值.
- $\sum_{k=j}^{i} A_k > M$ 这句话的意思是,$j$这个点是满足条件1中所有点中的最小点.
上面就是我们最优点所需要满足的性质,我们一个一个证明.
条件①,这个就不用证明了,题意提出的条件.
条件②和条件③证明,如下所示.
如果说最优点,不满足条件②和③,那么也就是说
因为条件③不成立了.那么我们看$j-1$点,显然$[j-1,i]$的和$\le M$,因为$j$点不是满足条件1所有点的最小点.
$$
F[j-1]+\max_{j \le k \le i}{A_k} \le F[j]+\max_{j+1 \le k \le i}{A_k}
$$
因为F数组必然具有单调递增性质,也就是$F[i] \le F[i+1]$.
但是如果说说这样的话,我们发现$j-1$这个点比$j$这个点更加最优,所以说假设失败.
通过以上的反证法,我们推出这三个条件&性质,是必须保证的.
因此我们得出.如果说$j_1 < j_2$而且$A_{j_1} \le A_{j_2}$ 那么显然$j_1$就是该淘汰的决策
二叉堆
综上所述,我们可以维护一个决策点$j$单调递增,数值$A_j$单调递减的队列.
决策点$j$单调递增,是为了保证条件三的最小点.因为队头的点,是最小的.
数值$A_j$的单调递减,就是为了保证条件二的最大值,因为队头的权值,是最大的.
但是这里,我们还有一个非常严重的问题没有解决,那就是我们发现队头的点,不一定可以保证.
$$
F[j]+\max_{j+1 \le k \le i}{A_k}
$$
请注意,这里的$j$就是队头.
代价不可以保证最小,是要出问题的,那么怎么办呢?
我们这里的单调队列,存储的候选集合中,必然有一个点会成为最后的胜利者,成为我们状态转移方程的最优点.
而最优点的判定,显然就是
$$
F[j]+\max_{j+1 \le k \le i}{A_k}
$$
值最小.
那么既然如此的话,我们为何不使用二叉堆,存储每一个$j$点所对应的这个值呢?这样我们二叉堆的堆顶,不就是最后的最优点了吗?
重点来了:我们让单调队列和二叉堆建立映射关系
我们知道答案必然出现在单调队列之中,所以说单调队列控制一个点的合法性,因为如果说一个点不在单调队列的话,那么显然和最优点是无缘的.
我们要的是最优点,不是一个答案区间,而这种最值性质,显然二叉堆可以胜任.所以说我们让二叉堆内,存储着每一个点所对应的权值
$$
F[j]+\max_{j+1 \le k \le i}{A_k}
$$
如果说单调队列里面的元素删除了,那么显然二叉堆的元素要删除.
同理,如果说单调队列的元素增加了,那么显然二叉堆的元素也要增加.
时间复杂度$O(nlogn)$
预处理
$$ \sum_{k=j+1}^{i}A_k \le M $$
这里面的最小点$j$的维护,我们可以通过每一步计算$F[i]$的时候,一起计算.
$$
\max_{j+1 \le k \le i}{A_k}
$$
$[j+1,i]$这个区间的最值,我们可以可以通过ST算法,进行预处理.
代码处理
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N],f[N],sum[N],head,tail,q[N];
void init()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if (a[i]>m)//无解情况
{
cout<<"-1";
exit(0);
}
sum[i]=sum[i-1]+a[i];
}
}
void work()
{
int pos=1,head=1,tail=0;
for(int i=1;i<=n;i++)
{
while(sum[i]-sum[pos-1]>m)
pos++;
while(head<=tail && a[q[tail]]<=a[i])
tail--;
q[++tail]=i;
while(q[head]<pos)
head++;
f[i]=f[pos-1]+a[q[head]];
for(int j=head;j<tail;j++)
f[i]=min(f[i],f[q[j]]+a[q[j+1]]);
}
cout<<f[n];
return ;
}
int main()
{
init();
work();
return 0;
}
//ST+堆操作,太难写了,我写了三个小时挂了,没办法QwQ
