感谢 @iknow 大佬指出本题代码一个巨大BUG,和数据点的小问题.

题目描述

给定一个长度为 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$显然是要满足一系列条件的.

1. 必须满足[j+1,i]这段区间的和$\le m$.(题意合法性)
2. $A_j=\max_{j \le k \le i}{A_k}$ 这句话的意思就是,第$j$个点,是[j+1,i]这个区间的最大值.
3. $\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;
#define int long long
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 ;
}
signed main()
{
    init();
    work();
    return 0;
}
//ST+堆操作,太难写了,我写了三个小时挂了,没办法QwQ