一些最值问题

Published: by Creative Commons Licence

  • Tags:

最小不能生成元素

题目1:给定$n$个面值为$a_1,\ldots,a_n$的硬币,其中$1\leq a_i\leq 10^9$。现在要求找到最小的非负价格$p$,满足不存在一个硬币子集,它们的和为$p$。

提供一个问题

我们可以用动态规划来计算,但是这样会导致状态数爆炸。

我们可以重新理解这个问题。我们驾车在$x$轴上行驶,初始的时候我们位于$0$处,并向正方向行驶。对于硬币$a_i$,我们可以理解是一桶位于$a_i-1$处的汽油,它可以让我们额外行驶$a_i$距离。问最远我们可以将车停在哪里(我们的实际答案还需要额外加1)。

这当然是一个贪心问题,我们可以$O(n)$求解。

题目2:给定$n$个面值为$a_1,\ldots,a_n$的硬币,其中$1\leq a_i\leq 10^9$。之后给定$q$个请求,请求分两类:

  1. 每个请求给定一个区间$l\leq r$,要求仅考虑硬币$a_l,a_{l+1},\ldots,a_r$,要求找到最小的非负价格$p$,满足不存在一个硬币子集,它们的和为$p$。
  2. 将第$i$个硬币的面额修改为$x$,其中$1\leq x\leq 10^9$。

其中$1\leq n,q\leq 10^5$。

提供一道题目

借助题目1的思路,我们可以把问题看成加油站问题。

由于涉及区间查询和单点修改,我们果断将结构丢到线段树上维护。每个线段树结点维护区间中的所有汽油信息。每个汽油有两个属性,所在位置和油量。

之后我们考虑如何实现上推操作(合并两个孩子的状态)。可以发现上推会导致顶点的汽油数爆炸,越往上单点维护的汽油数越多,上推难度也越大。但是可以注意到如果有一桶汽油,左边的所有汽油油量总和超过汽油所在的位置,那么这个汽油的油量可以直接加入到它左边的汽油中去,并且删除右边汽油。因此一个结点实际维护的汽油,一定满足左边的油量前缀和小于这个汽油的坐标,此时我们每次在尾部增加一桶汽油,那么总的油量会至少翻倍,而汽油的坐标不超过$10^9$,因此最多一个结点需要维护$\log_210^9$的汽油,约$30$个元素。

因此总的时间复杂度为$O((n+q)\log_2n\log_210^9)$。

几何

到中心最小距离问题

题目1:给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$,要求找到一个中心$(a,b)$,满足所有点到中心的曼哈顿距离之和最小。

由于是曼哈顿距离,所有不同的维度可以分别计算。

现在的问题变成了有$n$个数值$x_1,\ldots,x_n$,找一个中心值$a$,满足$\sum_{i=1}^n|x_i-a|$最小。这里我们直接取$a$为$x$的中间数即可。

题目2:在一个无穷大的棋盘上,给定$n$个网格点$(x_1,y_1),\ldots,(x_n,y_n)$,这些网格内放置了棋子。之后我们要将这些网格点移到到一块,即所有棋子占用的行恰好为连续的$n$行,而所有棋子占据的列恰好是连续的$n$列。每次移动棋子,可以将其移动到有公共边的网格中。问最少需要的移动次数。

这里我们可以把行和列拆开来计算。现在的问题是存在$n$个整数$x_1,\ldots,x_n$,很显然在移动的时候不会改变这些整数的顺序。要求找一个整数$a$(与$x_1-1$对齐),满足$\sum_{i=1}^n|x_i-(a+i)|$最小。我们修正一下公式可以发现为$\sum_{i=1}^n|(x_i-i)-a|$,因此$a$实际上是$x_1-1,x_2-2,\ldots,x_n-n$的中位数。

提供一道题目SRM 795 div1的第二题。

题目3:给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$,要求找到一个中心$(a,b)$,满足所有点到中心的2范数距离之和$J(a,b)=\sum_{i=1}^n(a-x_i)^2+(b-y_i)^2$最小。

考虑偏导数:

\[\frac{\partial}{\partial a}J(a,b)=2\sum_{i=1}^n(a-x_i)\]

由于极值点在偏导数为$0$的时候取到,因此有:

\[\begin{aligned} &2\sum_{i=1}^n(a-x_i)=0\\ \Rightarrow &na=\sum_{i=1}^nx_i\\ \Rightarrow &a=\frac{1}{n}\sum_{i=1}^nx_i \end{aligned}\]

同样有$b=\sum_{i=1}^ny_i$。

题目4:给定$n$个二维平面点$(x_1,y_1),\ldots,(x_n,y_n)$,要求找到一个中心$(a,b)$,满足所有点到中心的欧几里德距离之和$J(a,b)=\sum_{i=1}^n\sqrt{(a-x_i)^2+(b-y_i)^2}$最小。

可以证明函数$J$是凸函数,因此可以上三分套三分,梯度下降,模拟退火啥的。

凸函数的证明

一维点的匹配问题

题目1:给定序列$a_1,\ldots,a_n$以及$b_1,\ldots b_m$。要求找到一个1到m的置换$p_1,\ldots,p_m$。记置换的权重为$\sum_{i=1}^n |a_i-b_{p_i}|$。要求找到置换的权重的最小值。其中$1\leq n\leq m\leq 5000$。

不妨认为$a$和$b$序列都已经预先排好序了,那么最优解的情况下一定有$p_1<p_2<\ldots<p_n$。

因此我们可以记$dp(i,j)$表示从$1,\ldots,i$中选择$j$个作为$p_1,\ldots,p_j$,带来的最小权重。那么每个状态只需要考虑两种转移即可。总的时间复杂度为$O(nm+n\log_2n+m\log_2m)$。

题目2:给定序列$a_1,\ldots,a_n$以及$b_1,\ldots b_m$。要求找到一个1到m的置换$p_1,\ldots,p_m$。记置换的权重为$\sum_{i=1}^n |a_i-b_{p_i}|$。要求找到置换的权重的最大值。其中$1\leq n\leq m\leq 10^6$。

不妨认为$a$和$b$序列都已经预先排好序了。

考虑$a_i$和$a_{i+1}$,它们匹配的值为$b_{p_i}$和$b_{p_{i+1}}$。很显然如果$a_i\geq b_{p_i}$且$a_{i+1}\leq b_{p_{i+1}}$,那么我们交换$p_i$和$p_{i+1}$可以得到更大的一个权重。因此我们可以得出$a_i\geq b_{p_i}\Rightarrow a_{i+1}\geq b_{p_{i+1}}$。

根据上面的结论,我们可以找到一个点$k$,对于$i\geq k$,都有$a_i\geq b_{p_i}$,同时对于$i<k$,都有$a_i\leq b_{p_i}$。此时答案为$\sum_{i=1}^{k-1}(b_{p_i}-a_i)+\sum_{i=k}^n(a_i-b_{p_i})$。这时候我们要最大化$p_1,\ldots,p_{k-1}$,同时最小化$p_k,\ldots,p_n$,可以发现两者可以同时满足,此时若$i<k$,则$p_i=m+1-i$,若$i\geq k$,则$p_i=i-k+1$。

通过预处理前缀和,我们可以$O(n+m)$遍历所有可能的$k$。总的时间复杂度为$O(n\log_2n+m\log_2m)$。

概率和期望

概率

题目1:给定$n$个独立的随机变量$x_1,\ldots,x_n$,其中第$i$个随机变量从$1$到$t_i$中均匀随机取值,其中$m=\sum_{i=1}^nt_i$。要求对于$1\leq i\leq m$,求出$\max_{j=1}^nx_j=i$的概率。其中$1\leq n,m\leq 10^6$。

一种直接的想法是用DP的方式,但是这样会导致时间复杂度变成$O(nm)$。

一般遇到min-max概率或期望计算,都需要借助前缀和的技术。这里我们记$f(i)$表示最大值不超过$i$的概率。可以发现$f(i)=\prod_{t_j\geq i}\frac{i}{t_j}$。之后通过差分就可以得到$P(\max_{j=1}^nx_j=i)=f(i)-f(i-1)$。

上面过程的时间复杂度为$O(n\log_2n+m)$。

收集问题

题目1:一个游戏总共有$n$个奖章。每完成一局游戏,会固定得到一个奖章,其中得到的是第$i$个奖章的概率是$p_i$,其中$\sum_{i=1}^np_i=1$且$p_i>0$。要求计算搜集到所有奖章的期望游戏局数。其中$1\leq n\leq 25$。

这里我们可以使用min-max容斥。记$x_i$表示第$i$个奖章的获得时间。则

\[\begin{aligned} E[\max_{i=1}^nx_i]&=E[\sum_{I\subseteq N}(-1)^{|I|-1}\min_{i\in I}x_i]\\ &=\sum_{I\subseteq N}(-1)^{|I|-1}E[\min_{i\in I}x_i] \end{aligned}\]

其中$\min_{i\in I}x_i$表示多个奖章中最早获得奖章的获得时间。这等价于抛掷一枚不均匀硬币,第一次出现正面的时间,其等于$1/p$,其中$p$是出现正面的概率。因此化简可以得到:

\[\begin{aligned} \sum_{I\subseteq N}(-1)^{|I|-1}E[\min_{i\in I}x_i]&=\sum_{I\subseteq N}(-1)^{|I|-1}\frac{1}{\sum_{i\in I}p_i} \end{aligned}\]

上面的公式可以$O(2^n)$解决。

字典序

字符串合并

题目1:给定两个字符串$A,B$。以及一个空字符串$C$。之后我们可以不断的从$A,B$中选择一个非空字符串,将其头部元素删除并加入到$C$尾部。重复这个流程,直到字符串$A,B$都为空。要让$C$的字典序最大。

提供一道题目

首先说做法。每次比较$A$和$B$,将其中字典序较大的字符串的头部元素删除追加到我们的$C$中即可。这个过程,可以直接通过暴力比较$O(nm)$,或者一些复杂的后缀处理技术,比如后缀数组来提速,时间复杂度为$O(n+m)$。

下面说明一下这样做为什么是对的。

首先我们可以在两个字符串尾部都加上一个代表无穷小的哨兵字符,这样就可以避免讨论两个字符串一者是另外一者的前缀这种情况(但是两个字符串还是可能相同的)。很显然最后构建的字符串的尾部两个元素就是我们加入的哨兵字符。

记$inv(A_i)$表示$A_i$在最终结果($C$)中的下标。

如果$A=B$,很显然从哪个字符串头部删除都不会影响结果。下面认为$A\gt B$。我们记$t$为第一个不同的位置,即$A_1=B_1,\ldots,A_{t-1}=B_{t-1}$,但是$A_t\gt B_t$。

首先我们证明如果最终结果最优,则$A_t$一定出现在$B_t$之前。如果不是,记$L=inv(B_t)$,此时$B_t$在前。则对于所有$1\leq i\leq t$,我们将最终结果中$A_i$与$B_i$位置互换。此时可能发现换位后$B_i$出现在$B_{t+1}$之后的情况,我们可以将所有$B$占据的位置上的元素按照它们的下标重新排个序即可。可以发现修改后$C$的长度为$L-1$的前缀是不会改变的,而第$L$个元素从$B_t$变成了$A_t$,增大了,这说明了我们最终结果并不是最优的,与前提相悖。因此$inv(A_t)\lt inv(B_t)$。

之后我们证明至少存在一种最优结果,满足$inv(A_1)=1$,即$A$头部元素放在$C$的最前。证明方法也是构造性的,从任意一个最优解出发,如果此时最优解的头部元素是$B_1$而不是$A_1$,我们记$j$表示最大的下标,满足$inv(B_j)\lt inv(A_t)$。之后我们将$A_1$与$B_1$的位置互换。可以发现我们的最优解值是不会变的。但是这时候可能出现冲突,即$inv(B_1)\gt inv(B_2)$,$B_1$被交换到$B_2$之后了。我们可以继续让$B_2$与$A_2$交换位置。重复上面这个流程直到结束。很显然这个流程是会结束的,因为$B_j$不管是否交换都不会出现在$B_{j+1}$之后。而这个过程由于不会改变解的值,因此修改后的解依旧最优,且此时$inv(A_1)=1$。

因此根据上面的结果就可以放心大胆的使用贪心算法,因为无论如何都可以通过后续的手段将结果最优化。

题目2:给定$n$个字符串$s_1,\ldots,s_n$,要求将它们重新排列拼接,要求拼接得到的字符串字典序最大。

提供一道题目

考虑两个结果中相邻的字符串$A,B$。如果字符串$A$排在$B$之前,那么一定有$AB\leq BA$,否则交换后可以得到更优的结果。

而考虑到$AB\leq BA$等价于$A^+\leq B^+$,因此保证偏序关系的成立,因此我们可以使用比较算法。

时间复杂度为$O(nm\log_2n)$。

带关联最大和问题

题目1:给定一个序列$a_1,\ldots,a_n$,要求对于$k=1,\ldots,n$,计算仅从序列中取$k$个元素$a_{I_1},a_{I_2},\ldots,a_{I_k}$,满足$I_1<I_2<\ldots <I_k$,使得式子$\sum_{i=1}^ki\cdot a_{I_i}$最大,输出这个和。

提供一道题目

记$V(i)$表示仅取$i$个元素的最优集合,官方题解已经证明了$V(i+1)$可以通过向$V(i)$加入一个新元素得到。因此我们只需要每一步加入贡献最大的元素。

考虑已经加入$k$个元素,现在考虑元素$i$的贡献,它的贡献为$(p+1)a_i+\mathrm{suf}$,其中$p$表示$V(k)$中下标小于$i$的元素数量,而$\mathrm{suf}$表示下标大于$i$的元素和。

所以显然问题变成了有$n$条直线,第$i$条直线的公式为$a_ix_i+b_i$(这个$a_i$与题目中的$a_i$已经没有关系了,表示斜率),初始的时候$x_i=1$。要求支持三种操作:

  1. 删除一条直线。
  2. 将一段区间中的直线的$x$属性增大$1$
  3. 将一段区间中的直线的$b$属性增大$t$
  4. 查询当前贡献最大的直线。

这个用线段树是解决不了的,需要使用分块。一般分块结合排序的时间复杂度是$O(n\sqrt{n}\log_2n)$。但是由于属性$a$不会修改,因此我们实际上可以预先对$a$属性排序,相同$b$属性的我们取较大者即可。这样时间复杂度为$O(n\sqrt{n})$。

图论

拓扑序

题目1:给定一个包含$n$个顶点的树,记$G_v$表示将顶点$v$作为根,将所有边的改变为从父亲指向孩子的有向边。记$Topo(G_v)$表示这个有向图的总拓扑序的数目。要求找到$\max_{1\leq i\leq n}Topo(G_i)$。

提供一道题目

考虑存在边$(u,v)$,$Topo(G_u)$和$Topo(G_v)$的区别。

记$f(G_u,v)$表示以$u$为根时,删除$v$为根的子树后的拓扑序,而$s(G_u,v)$表示以$u$为根,以$v$为根的子树的大小。可以发现$Topo(G_u)=f(G_u,v)\times f(G_v,u)\times {n-1\choose s(G_u,v)}$。同理有$Topo(G_v)=f(G_v,u)\times f(G_u,v)\times {n-1\choose s(G_v,u)}$。此时有$\frac{Topo(G_u)}{Topo(G_v)}=\frac{s(G_v,u)}{s(G_u,v)}$。

通过上面式子可以发现,如果顶点$u$下有一个子树大小超过$\frac{n}{2}$,则这个顶点一定不是最优的。因此最优的点仅可能是重心,重心如果有两个,则任意一个重心都是最优的。我们只需要找到重心,之后算一下拓扑序就可以了。

最长公共子序列问题

题目1:给定长度为$n$的序列$a$和长度为$m$的序列$b$,要求找到它们的最长公共子序列的长度。其中$1\leq n\leq 1000$,$1\leq m\leq 10^6$。

最简单的LCS算法是定义$dp(i,j)$,表示$a$长度为$i$的前缀和$b$长度为$j$的前缀的最长公共子序列的长度。但是这样做的时间复杂度是$O(nm)$,太慢了。

由于LCS的长度不会超过$\min(n,m)$,因此我们定义$dp(i,j)$为$a$的长度为$i$的前缀和$b$的某个前缀拥有长度为$j$的公共子序列,$b$的前缀的最小长度。这样我们的状态仅$n^2$个。但是这样转移需要快速解决这样一个问题:记$f(i,x)$表示$b$中最小的下标$j$,满足$j>i$,且$b_j=x$。这个问题可以通过持久化技术解决,这样我们的每次dp转移的时间复杂度为$O(\log_2m)$,总的时间复杂度为$O(n^2\log_2m)$。

最小总和

树上最小总和

题目1:给定$n$个顶点的树,每个顶点$i$有一个权值$w_i$。现在在其中$k$个顶点$a_1,a_2,\ldots,a_k$上各有一个棋子,要求将这些棋子移动到$b_1,b_2,\ldots,b_n$上,其中在$a_i$的棋子需要移动到$b_i$,每次你只能选择一个棋子向某个邻近的顶点移动。称所有棋子所在的顶点的总和(一个顶点上可能有多个棋子,则统计多次)为潜能,要求移动过程中出现的潜能的最大值最小。问这个最小的潜能值是多少。这里$1\leq k\leq n\leq 1000$。

提供一道题目

首先我们可以用一个向量来维护所有顶点所在的顶点信息。接下来我们考虑贪心算法。记初始向量为$A$,$f(A,t)$表示字典序最小的向量(两个顶点的排序规则是第一关键字为权值,第二关键字为编号),满足在潜能上限不超过$t$的前提下能从$A$通过若干步骤转移到$f(A,t)$。

考虑到不同的棋子的移动是独立的,因此我们可以同时让所有棋子移动到最小的顶点。考虑给定潜能上限$t$,之后我们贪心将所有顶点向具有更小权重的顶点移动(在不违背上限的前提下)。这里我们给出了计算$f(A,t)$的算法,时间复杂度为$O(n^2\log_2n)$。

很显然在给定潜能上限$t$的前提下,是否能从$A$转移到$B$等价于$f(A,t)=f(B,t)$。我们要找到最小的$t$,满足这个公式。这里可以使用二分,则时间复杂度为$O(n^2(\log_2n)^2)$。但是我们可以通过增量的方式,不断增大$t$,同时考虑造成的影响,这样就能去掉二分,将时间复杂度优化到$O(n^2\log_2n)$。

给定和最大乘积

题目1:给定总和$m$,要求选择一个$n$并找到一组正整数$x_1,\ldots,x_n$,满足$\sum_{i=1}^n x_i=m$,且$\prod_{i=1}^nx_i$最大化。其中$1\leq m\leq 10^{18}$,输出$(\prod_{i=1}^nx_i)\mod p$,其中$p$为某个正数。

当$m\leq 1$的时候,问题是很简单的,这里不讨论。

首先我们可以发现对于$t\geq 4$,我们始终可以将其拆分为$t-2$和$2$,且二者的乘积不小于$t$。因此我们可以断言$x_i$仅可能为$2$或$3$。

同时可以发现当$2$出现达到$3$次的时候,由于$2^3<3^2$,因此我们可以将$3$个$2$替换为$2$个$3$。故我们只需要暴力枚举$2$出现的次数,仅可能为$0,1,2$次。

考虑$r=m\pmod 3$。

  • 如果$r=0$,那么$2$只可能出现$0$次。
  • 如果$r=1$,那么$2$只可能出现$2$次。
  • 如果$r=2$,那么$2$只可能出现$1$次。

这样我们不需要比较操作就可以得到最优解。

置换与交换

置换与交换类型的问题非常常见,问题一般就是现在有一个置换,每次操作允许交换置换中的两个元素。问最少排序需要的步骤数。

这个东西题目出的非常多。

题目1:给定一个$1,\ldots,n$的置换$p$,每次操作允许交换两个元素,要求计算将其排序的最少步骤数。

创建一个包含$n$个顶点的有向图,并对于$1\leq i\leq n$,加入边$(i,p_i)$。图可以分成若干个环,记环的数目为$C$。

考虑一次操作,最多使得一个环分裂成为两个,或者将两个环合并为一个。由于当置换有序的时候,总共会存在$n$个环,因此答案为$n-C$。

时间复杂度为$O(n)$。

题目2:给定$n$个二维平面点,不存在任意三个点共线。第$i$个点上写着数字$a_i$,且$a_1,\ldots,a_n$是$1,\ldots,n$的一个排列。每次操作选择两个点,在它们之间画一条线段,之后交换两者上写的数字。要求执行一些操作后,使得对于$1\leq i\leq n$满足第$i$个点上写着$i$,且画的线段除了端点外不会相交。

提供一道题目题目

首先我们不考虑那些初始就写着目标值的点。建环后可以发现所有环的长度都至少为$2$。

接下来我们将所有环合并。具体的做法就是我们选择一个最靠下的点$z$(有多个就选择最靠左的)。之后将其余点按照以$z$为中心的极角排序。

之后可以按序遍历其余点,如果点$i$和点$i+1$不在同一个环中,就交换这两个点。

可以发现如此操作后,所有点都在一个环上了,并且出现的线段都是在相邻极角之间。这意味着$z$到任意点的射线都不会与这些线段相交。

之后问题我们可以把$z$与$z$上所写数字对应的点交换,重复这个过程直到$z$和$z$上所写数字相同。

时间复杂度为$O(n\log_2n)$。

最小差值问题

题目1:给定两个长度为$n$的序列$a_1,\ldots,a_n$和$b_1,\ldots,b_n$,可以任意选择一些下标,如果你选择了$i$,则会将$a_i$提换为$b_i$。要求让$a$中最大值和最小值的差值尽可能小,找到最小的差值。其中$1\leq n\leq 10^6$,$-10^9\leq a_i\leq 10^9$。

首先我们可以不妨认为对于所有$1\leq i\leq n$,都有$a_i\leq b_i$(否则你先交换两个数即可)。之后我们暴力枚举允许出现的最小值,并维护当前的最大值。由于最小值只有$2n$种情况,因此只会发生$2n$次的最小值替换,我们从小到大考虑这些最小值。假设我们选择了最小值$x$,那么由于我们现在维护的一些值可能因为小于$x$因此变得非法,我们需要尝试替换为较大的值。我们可以用一个最小堆来维护这些候选人,同时由于最大值始终递增,只需要一个变量维护即可。总的时间复杂度为$O(n\log_2n)$。

题目2:给定长度为$n$的序列$a_1,\ldots,a_{n}$。要求将这些数分成任意组,每组至少有一个数,最多有两个数。要求组中值之和的最大值和最小值的差距尽可能小,输出这个最小值。其中$1\leq n\leq 5000$,$-10^9\leq a_i\leq 10^9$。

提供一道题目

假设$a$是从小到大排序的。

假设最终被配对的数从小到大排序为$b_1,\ldots,b_k$。如果$b_1$与$b_k$不配对,而$b_1$与$b_i$,$b_j$与$b_k$配对,那么我们重新将$b_1$与$b_k$配对,而$b_i$与$b_j$配对,由于$b_1+b_i\leq b_1+b_k,b_i+b_j\leq b_j+b_k$。因此新的配对不会违背任何约束。继而我们可以推出$b_i$与$b_{k+1-i}$配对。

首先如果所有数都不是正数,那么我们将所有数全部取反,这样得出的结果是不变的。

当所有数都非负的时候。如果存在$i<j$,$a_i$未参加配对,但是$a_j$参加了,那么我们可以知道最小值不超过$a_i$。这时候我们将$a_i$与$a_j$位置交换,可以发现新的结果不会变坏。因此我们可以断言参与配对的元素一定正好形成$a_1,\ldots,a_n$的一个前缀。我们可以暴力枚举所有前缀并计算差值,这样就提供了一个$O(n^2)$的算法。

最后我们考虑$a$中同时有正数和负数的情况,即$a_1<0$且$a_n>0$。那么可以发现$a_1$和$a_n$必定都参与匹配,根据第一块内容可知$a_1$与$a_n$在同一组情况是最优的。弹出$a_1$与$a_n$合并为同一组,重复这个流程直到$a$中只剩下非负或非正数,记录$L,R$为已知组形成的范围。之后用之前提到的算法即可$O(n^2)$解决剩下的内容。

区间减法问题

题目1:给定长度为$n$的序列$a_1,\ldots,a_n$,要求执行下面操作若干次,使得序列中所有元素都变成$0$。

  • 每次操作选择一段连续的区间,将区间中所有元素减少1。

要求找到达成目标的最小操作数,并输出。其中$1\leq n\leq 10^6$,且$1\leq a_i\leq 10^9$。

引入一个新变量$a_0=0$,如果存在$i\geq 1$,满足$a_i>a_{i-1}$,那么很显然我们至少需要有$a_i-a_{i-1}$个操作,起始于下标$i$。

于是我们找到了一个结果的下界$\sum_{i=1}^n\max(a_i-a_{i-1},0)$。接下来我们还要证明这个下界同时是可以达到的。

事实上,如果$a_i\leq a_{i-1}$,那么我们可以继承所有之前未终止的操作。而如果$a_i>a_{i-1}$,那么我们可以继承之前的$a_{i-1}$个操作,并额外创建$a_i-a_{i-1}$个操作,以$i$作为起始。很显然这种方式得到的操作数为$\sum_{i=1}^n\max(a_i-a_{i-1},0)$。

因此答案为$\sum_{i=1}^n\max(a_i-a_{i-1},0)$,时间复杂度为$O(n)$。

题目2:给定长度为$n$的序列$a_1,\ldots,a_n$,要求执行下面操作若干次,使得序列中所有元素都变成$0$。

  • 每次操作选择一段长度在至少为$L$,且最多为$R$的连续的区间,将区间中所有元素减少1。

要求找到达成目标的最小操作数,并输出。其中$1\leq n\leq 10^6$,且$1\leq a_i\leq 10^9$,$n\geq R\geq 2L-1$,$L\geq 1$。如果无解则输出$-1$。

提供一道题目

首先考虑当$R=N$的时候,如何解决这个问题。很显然我们可以贪心来做。具体就是我们维护一个集合$S$,$S$中存储所有未闭合的操作区间。之后从左到右扫描我们的序列$a$。考虑现在处理的是$a_i$,这时候有两种情况:

  • 一种是$|S|>a_i$,这时候我们必须闭合$S$中的一些序列。我们可以随意挑一些长度至少为$L$的区间,关闭,并从$S$中移除。如果剩下的都是长度不超过$L$的区间,那么就无解。
  • 另一种情况就是$|S|<a_i$,这时候我们必须新建一些操作区间,我们可以插入$a_i-|S|$个新的操作区间(注意开始下标相同的操作区间,我们可以合并并记录它的重复次数),以$i$作为起始下标。

在扫描完所有的元素后,我们要关闭集合$S$中所有的操作区间(如果有长度小于$L$的区间,则无解)。

上面的算法正确性和最优性是很显然的。

下面我们考虑$R$任意的情况。这时候我们实际上可以认为一个操作区间长度可以超过$R$,只不过需要额外的费用而已。事实上,如果一个区间长度为$x\geq L$,那么我们一定可以将它分解为$\lceil x/R \rceil$个操作,具体就是按$R$切分成若干段,很显然只有最后一段长度$x \pmod R$可能小于$L$,这时候由于$R+(x\pmod P)\geq 2L$,因此我们可以将最后一段和倒数第二段合并后重新分解为两端长度满足条件的操作序列。同时可以发现继续复用之前遗留的操作区间比新建操作区间一定更优。

因此我们可以按照上面的逻辑来实现我们的算法,只不过在从$S$中删除序列的时候,应该贪心删除$b-i\pmod R$最小的操作区间,其中$b$表示区间的开始下标。

我们可以用一个队列来维护长度小于$L$的操作区间,并用链表来维护长度达到$L$的操作区间,用VEB Tree可以$O(\log\log R)$找到某个点的前驱和后继。因此总的时间复杂度为$O(n\log\log R)$。