一些贪心问题

Published: by Creative Commons Licence

  • Tags:

拟阵

拟阵可以用于证明很多贪心策略的正确性。

这部分的内容主要来自于【洛谷日报#181】拟阵与最优化问题,我主要做了整理以及重写了所有的证明。

设$S$是一个集合,而$L$是$S$的子集族(由$S$的子集组成的一个集合)。我们称$(S,L)$是拟阵,如果它满足下面的性质:

  1. $S$是有限集。
  2. ${\emptyset}\in L$
  3. 遗传性:若$A\subseteq B$,则$B\in L\rightarrow A\in L$。
  4. 交换性:若$A,B\in L$,且$|A|<|B|$,那么一定存在一个元素$x\in B\setminus A$,使得$A\cup {x}\in L$。

集合$L$中的每个元素,都称作独立集。如果$A$是独立集,且存在某个元素$x\in S$,使得$A\cup {x}$也是独立集,那么称$A$是可扩展的,否则称$A$是极大独立集。

命题1:$L$中的所有极大独立集拥有相同大小

证明:如果存在两个极大独立集$A$,$B$,且$A$的大小小于$B$,则根据交换性,我们可以从$B$中找到一个元素扩展$A$,这与$A$是极大独立集的前提相悖。

现在考虑我们选择了一个权值函数$w:S\rightarrow \mathbb{R}^+$,我们利用这个函数为每个$S$中的元素赋予一个正数权值。同时我们定义一个独立集的权值为其中所有元素的权值之和,即:$w(A)=\sum_{x\in A}w(x)$。如果对于某个独立集$A$,它的权值大于等于所有$L$中独立集的权值,那么称$A$是最大权独立集。

命题2:最大权独立集一定是极大的

证明:假设$A$是最大权独立集且不是极大的,$B$是任意极大独立集,我们可以找到$B$中的某个元素$x$来扩展$A$,考虑到$w(x)>0$,因此$w(A\cup {x})=w(A)+w(x)>w(A)$,这与$A$是最大权独立集相悖。

这里我们可以直接提供一个算法来计算最大权独立集:

maximumWeightIndependentSet(S, L){
    将S中的元素按照权值从大到小进行排序;
    A = {};
    //从前到后遍历S
    for(x : S){
        //如果A与{x}的并集是独立集
        if((A+{x}) in L){
            A = A + {x};
        }
    }
    return A;
}

很显然这个算法的时间复杂度为$O(n(log_2n+m))$,其中$n=|S|$,$m$是每次判断某个集合是否是独立集的时间复杂度。

命题3:上面的maximumWeightIndependentSet返回的是最大权独立集

证明:

我们这边需要利用归纳法进行证明。记$S_i$表示由$S$中权值最大的前$i$个元素组成的集合,$L_i$表示$L$中所有仅包含$S_i$中元素的集合组成的族,记录$A_i$表示拟阵$(S_i,L_i)$的最大权独立集。在处理完$S_0$后,很显然此时$A_0$是空集。

考虑处理完前$i$个元素后,此时$A_i$是$S_i$的最大权独立集。现在我们考虑集合$A'=A_i\cup {x}$,其中$x$是$S$中权重第$i+1$大的元素。

如果$A'\in L$,那么我们可以直接断定$L_{i+1}$的极大独立集的大小等于$|A'|$,由于$L_i$的极大独立集大小为$|A_i|=|A'|-1$,因此$A_{i+1}$一定包含$x$,由于$A_{i+1}\setminus {x}$是$L_i$中的某个独立集,其权值不可能超过$A_i$。因此在这种情况下一定有$w(A_{i+1})=w(A')$。

现在考虑$A'\notin L$,那么我们可以断定$L_{i+1}$的极大独立集的大小等于$|A_i|$。若$A_{i+1}$包含$x$,那么$A_{i+1}\setminus {x}$是$L_i$的某个独立集(非极大),同时由交换性可知:我们可以从$A_i$中选出一个元素加入到$A_{i+1}\setminus {x}$中。这样得到的集合是$L_{i}$的某个独立集,且权重要大于等于$A_{i+1}$,小于等于$A_i$,因此可以得出$w(A_i)=w(A_{i+1})$。

因此利用归纳法我们就证明了算法的正确性。

例子1:拟阵解决最小生成树问题

最小生成树问题:给定无向图$G=(V,E)$,保证所有顶点连通。要求从边集中恰好选出$|V|-1$条边构成一株树,并且保证所有边的权重和最小。

首先我们先建立拟矩$(S,L)$。记录$S=E$。对于$S$的子集$X$,如果$X$中不出现可以构成环的边序列,那么$X\in L$。

显然$S$是有限集,且空集属于$L$。

很显然$L$是满足遗传性的,因为如果一组边不形成环,删除任意边后当然还是不会出现环的。

接下来我们证明$L$也满足交换性。考虑两个边集$A$,$B$,二者都是构成森林的边集合,且$|A|<|B|$。我们可以用下面流程找到可以加入$A$的$B\setminus A$中元素$x$。

  1. 记$X=A$

  2. 遍历$B$中元素,记当且遍历的边为$b$。

    2.1. 如果$b$加入$X$中后会出现环,此时环中一定会包含一条$A$中的边$a$,从$X$中删除$a$后并加入$e$。回到步骤2。

    2.2. 否则$b$加入$X$中不会出现环,那么此时我们直接得到了$x=b$。

由于$|B|>|A|$,因此这个流程一定会在2.2处结束。利用这个构造性算法我们可以保证$L$满足交换性。

到此我们证明了$(S,L)$是一个拟阵。下面我们来解决最小生成树问题。

由于我们掌握了求拟阵的最大权独立集的算法,我们可以应用到这里。要让和最小,等价于让和的相反数最大。对于边$i$,如果原本权重为$w(i)$,那么我们定义一个新的权重函数$w'(i)=\inf-w(i)$。其中$\inf$是一个足够大的常数,能够保证$w'(i)>0$。

很显然最大权独立集一定是极大独立集,而极大独立集的大小一定为$|V|-1$,能够正好构造一株树。而真实的权重为最大权独立集的权重减去$\inf \cdot (|V|-1)$后取反即可。

例子2:任务调度问题

任务调度问题:给定$n$个任务,每个任务花费1单位时间,第$i$个任务要求在$t_i$时间之前完成,否则罚款$c_i$,问如何调度任务的处理顺序可以使得总罚款最小。

首先我们建立拟阵$(S,L)$,记录$S$为任务集合。对于$S$的子集$X$,如果我们能够通过调度使得所有$X$中的任务都能在截止时间前完成,那么$X\in L$。

显然$S$是有限集,且空集属于$L$。

很显然如果$X$能够通过调度在截止时间前完全执行完,那么从中删除几个任务后,肯定能保证剩余的任务能全被执行完,因此遗传性得到满足。

现在考虑两个$L$中元素,$A$与$B$,其中$|A|<|B|$,现在我们希望能找出能加入$A$的$B\setminus A$的元素$x$。记录$A$中截止时间最晚的任务的截止时间为$t_A$,而$B$中截止时间最晚的任务的截止时间为$t_B$。如果$t_A<t_B$,那么将$x$就是$B$中截止时间最晚的任务。否则,我们有$t_A\geq t_B \geq |B| > |A|$,此时我们记录$x$为$B$中截止时间最晚的任务,可以发现在$x$加入$A$后,所有$A$中时间小于$t_B$的任务的执行顺序不变,时间大于等于$t_B$的任务都延迟一秒后执行。如果此时出现矛盾,即存在某个时刻$t\geq t_B$,满足排在它之前的任务数大于等于$t$,但是这就意味着$A\cup {x}$中至少包含$t+1\geq t_B+1\geq |B|+1$个任务,这与之前假设的$|A|<|B|$不符。到此,交换性得到证明。

之后我们考虑如何建立权重函数,要让罚款最小,而总罚款是固定的,等价于让按时完成的任务的总罚款最大,即我们可以选择每个任务的权重为其罚款。

之后我们只需要找到拟阵的最大权独立集即可。

前缀匹配问题

考虑下面问题:

形态1:电影院有$n$个人和$n$把椅子,椅子编号为1到n,对于第$i$个人,他希望能坐在前$a_i$把椅子中的一把椅子上,不然他会不满意。现在要求我们安排这$n$个人的座次,要求不满意的人数最少。

很容易看出,将人和椅子建立二分图,就是一个简单的二分图匹配问题。

但是,假如我告诉你$n=10^6$的时候,是不是就发现这问题不简单了。

观察一下这个问题与经典的二分图匹配问题有哪些区别,最重要的区别就是每个人能够匹配的椅子都是某个前缀。因此我们可以贪心地解决这个问题。

因此算法就得出来了,我们把所有人按$a_i$进行排序,之后从前往后遍历每一张座位,如果有座位在,我们让所有能坐在该座位上的人中$a_i$属性最小的人坐上去。(假如最优方案由编号更大的人坐在这里,我们交换两人座位方案依旧可行且最大匹配不变)

下面强化一下这个问题:

形态2:电影院有$n$个人和$n$把椅子,椅子编号为1到n,对于第$i$个人,他希望能坐在前$a_i$把椅子中的一把椅子上,不然他的不满意值会变成$u_i$(如果满意则为0)。现在要求我们安排这$n$个人的座次,要求所有人不满意值最小。

这个问题是带权二分图匹配,经典做法就是直接上最小费用最大流。但是这里的$n=10^6$,因此是不可行的。

实际上问题还是可以贪心解决。我们先对所有人按照$a_i$进行排序。之后扫描所有椅子,让所有能坐上这把椅子的人中$a_i$最小的那个人坐上。但是不同的是,当处理完第i把椅子后,我们需要考虑所有最后能匹配的椅子为i的人,他们该何去何从。我们会试图用他们替换已经坐上椅子中的人中$u_i$最小的那个,假如比我们现在手头的候选人的$u_i$更小,那么就替换它,否则我们的候选人将永远失去坐上椅子的机会。

注意到算法只是用到了$u_i$属性的偏序关系,真实值并不会影响结果,而这一点会直接决定下一个问题的解法。

下面考虑一下这个问题的变形:

形态3:电影院有$n$个人和$n$把椅子,椅子编号为1到n,对于第$i$个人,他希望能坐在前$a_i$把椅子中的一把椅子上,或者坐在后$b_i$把椅子中的一把椅子上,不然他会不满意。现在要求我们安排这$n$个人的座次,要求不满意的人数最少。

这个问题不仅存在前缀,还存在后缀,怎么解决呢。我们先分配前缀,再分配后缀座位。对于一个人,如果$b_i$越大,那么在分配前缀的阶段中,即使被淘汰,成本也越小。因此我们可以规定一个人被淘汰的费用为$-b_i$,那么分配前缀的过程实际上就是一个最小费用最大匹配,而分配后缀的过程就是一个普通的最大匹配。

形态4:电影院有$n$个人和$m$把椅子,椅子编号为1到m,对于第$i$个人,他希望能坐在前$a_i$把椅子中的连续的$c_i$把椅子上,不然他会不满意。现在要求我们安排这$n$个人的座次,要求不满意的人数最少。

这个问题中,一个人可以分配到不止一把椅子。我可以把第i个人占用的$c_i$个座位理解成为让他没有椅子坐的费用为$-c_i$。之后就是一个带权的前缀匹配问题了。

选择商品问题

问题1:有$n$类商品,第$i$类商品有$c_i$件。现在你必须从这些商品中选择$k$件商品。假设第$i$类商品我们选择了$a_i$件,那么我们的收益为$\sum_{i=1}^na_i(c_i-a_i)$,问最大收益是多少。其中$n\leq 10^5, 1\leq k\leq \sum c_i\leq 10^5$

记录$f(x)=x(c-x)$,那么可以发现$f'(x)=c-2x$是单调减少的,因此有$f(x)-f(x-1)>f(x+1)-f(x)$。于是我们可以将第$i$类商品分成$c_i$个商品,分出的第$j$种商品的收益为$j(c_i-j)-(j-1)(c_i-(j-1))$。之后贪心选择最大的$k$件商品即可。

问题2:有$n$类商品,第$i$类商品有$c_i$件。现在你必须从这些商品中选择$k$件商品。假设第$i$类商品我们选择了$a_i$件,那么我们的收益为$\sum_{i=1}^na_i(c_i-a_i)$,问最大收益是多少。其中$n\leq 10^5, 1\leq k\leq \sum c_i\leq 10^9$

和问题1类似,但是数据范围大了很多。我们发现随着选择次数的增加,选择的所有商品中收益最小的商品的收益一定递减,因此我们可以二分收益最小的商品的收益,每次二分检查的时间复杂度为$O(n\log_2M)$,因此总的时间复杂度为$O(n(\log_2M)^2)$,其中$M=\sum c_i$。

水位问题

题目1:有$n$天,第$i$天的水位高度为$h_i$。对于第$i$天,如果水位高度之前没有出现过,则第$i$天结束的时候会在$h_i$处划上一条横线。记$n$个数$p_1,\ldots, p_n$,其中$p_i$表示第$i$天时,高于当前水位的刻度线的数目。记$q_1,\ldots,q_n$,其中$q_i$表示第$i$天时,低于当前水位的刻度线的数目。已知$p$序列,现在希望求$q$序列之和的最小值

这道题可有这样做,记$t_i$表示第$i$天结束后的刻度线总数。那么会发现$q_i=t_i-1-p_i$,即要让$\sum_{i}q_i$最小,则等价于让$\sum_{i}t_i$最小。

这样我们就可以用贪心算法来解决这个问题了。首先如果能不创建水位线,我们就不创建,直到发现$p_i$比当前水位线多的时候我们再创建。发现如果第$i$天创建一个新的水位线的话,那么这个水位线对结果的贡献为$n-i+1$,那么对于没有新建水位线的日子,我们要倒序处理。时间复杂度为$O(n)$。

题目2:有$n$天,第$i$天的水位高度为$h_i$。对于第$i$天结束的时候会在$h_i$处划上一条横线。记$n$个数$p_1,\ldots, p_n$,其中$p_i$表示第$i$天时,高于当前水位的刻度线的数目。记$q_1,\ldots,q_n$,其中$q_i$表示第$i$天时,低于当前水位的刻度线的数目。已知$p$序列,现在希望求$q$序列之和的最小值

问题2和问题1稍微有些不同,就是不管这条刻度线是否之前出现过,都会划上一条新的刻度线。

同样我们需要定义一个新的变量$t_i$,其中$t_i=\sum_{j<i}[h_j=h_i]$。那么我们会发现:$t_i+p_i+q_i=i-1$。因此要让$q_i$最小,等价于让$t_i$最大。

我们在处理完每一天后,我们将水位按照高度从高到低排序。这里我们可以发现,对于第$i$天,假如之前几天的水位中正好能找到$p_i$个较大的水位,满足后面的所有水位高度都小于前$p_i$个水位的高度,那么我们可以将第$i$天的水位设置为和第$p_i+1$大的水位相同即可。但是如果不存在,则存在若干个和第$p_i$大水位相同高度的水位,我们需要将时间靠后的一些水位上升高度。

上述的所有操作都可以通过平衡树实现,时间复杂度为$O(n\log_2n)$。

一类树上选根问题

题目1:给定一个拥有$n$个顶点的树,其中第$i$个顶点有一个非负权重$w(i)$。现在要求选择一个树根$r$,记$d(i)$为第$i$个顶点到$r$的距离,定义费用为$\sum_{i=1}^nd(i)w(i)$,要求使得费用最小。

由于费用和根顶点挂钩,我定义$R(x)$表示以$X$顶点作为根的费用。树上选根问题的核心是,当我们选到费用最小的树根$r$的时候,我们观察$r$的邻近顶点,会发现这些顶点实际上的费用都不小于$r$的费用。

下面讨论一个直观的贪心算法。考虑任意一条边$(u,v)$,若$u$离$r$更近,那么我们可以断言$R(u)\leq R(v)$。为啥?如果我们将$(u,v)$删除,会得到两个连通块,包含$u$的叫做$u$连通块$B(u)$,包含$v$的叫做$v$连通块$B(v)$。当从$v$切换根到$u$的时候,这时候$v$连通块中顶点的距离全部$+1$,而$u$连通块中顶点的距离全部$-1$。而这对费用的影响是$R(u)=R(v)+\sum_{x\in B(v)}w(x)-\sum_{x\in B(u)}w(x)$。而后面两项的和一定不超过$0$,因为$r\in B(u)$,而$r$的任意某个孩子代表的子树,都必定不超过树上所有顶点总权的一半(否则我们可以取它的总权最大的孩子作为根),而$B(v)$仅相当于$r$的某个孩子的子树下的某个更小的子树而已,考虑到所有顶点权重非负,因此一定有$\sum_{x\in B(v)}w(x)\leq \sum_{x\in B(u)}w(x)$。

因此这个问题就得到了做法,遍历树,当遍历到顶点$x$时,我们考虑所有连接$x$和孩子的边,判断$r$在哪个孩子下面即可,时间复杂度为$O(n)$。

题目2:给定一个拥有$n$个顶点的树,其中第$i$个顶点有一个非负权重$w(i)$。现在要求选择一个树根$r$,记$d(i)$为第$i$个顶点到$r$的距离,考虑某个顶点$v$,记根到$v$的唯一路径为$r=v_0,v_1,\ldots,v_k=v$,定义$v$的费用为$V(v)=\sum_{i=0}^ki\cdot w(v_i)$,定义树的费用为$R(r)=\sum_{i=1}^nV(i)$,要求找到根使得树的费用最小。

这道题和题目1实际上没什么差别,只是搞得复杂一些而已。我们记$size(i)$表示以$i$为根的子树大小,同时定义$s(i)=\sum_{c\in subtree(i)} size(i)w(i)$,这个可以通过一次DFS算出来。

考虑任意一条边$(u,v)$,其中$r$在$u$连通块中,因此从$v$切换到$u$的新费用为$R(u)=R(v)-S(u)+S(v)$,而这里一定有$S(u)\geq S(v)$,证明方法和问题1类似。

因此做法还是DFS选择根即可,时间复杂度为$O(n)$。

提供一道题目:SRM763 RootItRight。

题目3:给定$n$个顶点组成的树,每条边都有边权。记顶点$1$为根,且除了顶点$1$外其余顶点的度数都不超过$2$。现在要求在这$n$个顶点中选择$k$个顶点,要求这$k$个顶点两两之间距离之和最小。

一道CF题目

一类反悔问题

反悔问题一般都是非常难想到的,证明也不太好证。这里只能记下来,之后拿来套用。

考虑这样一个问题,有一个环,环上有$n$个点,顺时针编号为$1,2,\ldots,n$,第$i$个点的点权为$w_i$。现在要求从这些点中正好选$k$个顶点,且要求选择的任意两个点不相邻,问选择的点的总权和最大为多少。一道题目

这个问题自然能让人想到一个$dp$方法,时间复杂度为$O(nk)$,不是很理想。我们可以用贪心算法来解决这个问题,每次选择权重最大的顶点,之后将其删除,并将其两侧的点合并为一个点,现在我们要做的就是重复这个过程$k$次,而答案就是删除的顶点的总权和。这样我们只需要维护一个树集,时间复杂度为$O((n+k)\log_2n)$。

再考虑一个问题,有$n$天,第$i$天股票的价格为$p_i$,$0<p_i$。每天你要么什么都不做,要么买入一份股票,要么卖出一份股票。问你最多能赚多少钱。

这个问题也可以用$dp$做,但是时间复杂度为$O(n^2)$。我们可以用贪心的做法做,将每天的股票看作一次买入的机会,但是我们直到真正要卖股票的时候才买入。第$i$天的时候,我们首先可以得到第$i$天的股票买入机会。如果我们发现手头的机会中,某一天入手的价格低于$p_i$,我们可以消耗掉那次机会,在该天买入并在今天卖出,否则我们就不卖。需要注意的是当我们在第$i$天以价格$p_i$卖出第$j$天的股票时,应该允许我们以$p_i$重写买回第$j$天的股票。实现只需要维护一个最小堆,时间复杂度为$O(n\log_2n)$。

连续子序列和问题

考虑一个序列$a_1,\ldots,a_n$。我们希望找到某个总和最大的连续子序列(可以为空)。

记$L(i)$表示以$i$为子序列的右边界,所有的连续子序列中总和最大的子序列的左边界。可以发现$L(i)$是非严格递增函数。且如果$a_l+\ldots+a_r>0$,则$r+1$不是$L$的有效取值。我们这里记$S(i)={j| f(j)=i}$,可以发现$S(i)$中的元素构成某个连续的下标区间(可能为空),且对于任意$i\neq j$,都有$S(i)\cap S(j)=\emptyset$。

上面的观察给我们提供了一个非常简单的贪心算法:维护一个当前最大子序列和$s$,之后从左到右扫描所有的元素,对于$a_i$,将$s$更新为$\max(s+a_i,0)$。这个算法显然是$O(n)$的。

问题1:给定一个序列$a_1,\ldots,a_n$,其中每个元素为$-1$或$1$,其中有些数值为$?$表示未知。现在要求我们将每个$?$替换为$-1$或$1$,记$f(l,r)=|\sum_{i=l}^ra_i|$,要求$g(S)=\max_{l\leq r}f(l,r)$尽可能小,输出$g(S)$

Atcoder的原题

我们可以将问号都替换为$-1$,之后找到最大连续子序列和,记作$T$,类似的将问号都替换为$1$,之后找到最小连续子序列和,记作$B$。很显然结果的下界为$\max(T,-B)$,我们希望让答案尽可能接近这个下界。

我们是否能让答案恰好为$\max(T,-B)$,是有可能的。记$R(i)$表示以$i$为右边界的最大子序列和,$r(i)$对应的为最小子序列和,同时记$L(i)$表示以$i$为左边界的最大子序列和,$l(i)$为最小子序列和。

考虑任意两个下标$i<j$:

  • 若$R(i)=T$且$L(j)=T$,且$j-i$与$T$同奇偶,则答案至少为$T+1$。
  • 若$r(i)=B$且$l(j)=B$,且$j-i$与$B$同奇偶,则答案至少为$-B+1$。
  • 若$R(i)=T$且$l(j)=B$,且$T=-B$,且$j-i$是偶数,则答案至少为$T+1$。
  • 若$r(i)=B$且$L(j)=T$,且$T=-B$,且$j-i$是偶数,则答案至少为$-B+1$。

上面的过程我们可以$O(n^2)$解决,但是注意到我们实际上只需要维护奇偶性,因此可以优化到$O(n)$解决。

前缀和最小费用

给定$n$个非负未知数数$a_1,\ldots,a_n$,要求为每个数赋值。且每个数都有个要求,表示$\sum_{i=1}^ja_j\geq d_j$。要求找到一组赋值方案,满足所有条件的前提下,$\sum_{i=1}^nc_ia_i$最小。其中$c_i\geq 1$

我们可以从前往后扫描,设现在处理的数是$a_i$,记现在前缀和为$P_{i}$。则我们考虑两种情况:若$P_{i}\geq d_i$,我们就什么数都不放;否则我们选择$c_j$最小的$j$,满足$j\leq i$,并让$a_j$增大$d_i-P_{i}$。

上面的是一个贪心算法,我们可以容易证明它的正确性,我们尽可能推迟做决策的时机,这样可供选择的项也越多。

在一颗包含$n$个结点的树上,以$1$作为根结点。第$i$个结点有一个非负权值$a_i$。要求为每个权值赋值。且每个结点都有一个要求,表示从这个结点到根结点的唯一路径上所有结点的权值和至少为$d_j$。要求找到一组赋值方案,满足所有条件的前提下,$\sum_{i=1}^nc_ia_i$最小。其中$c_i\geq 1$

一道题目SRM744 CoverTreePaths。

这道题也是类似,我们按照拓扑序进行处理,可以得知顶点$i$处需要在到根的路径上选择一个顶点,并将其权值增加$t_i$。

我们采用自底向上的技术来解决这个问题。考虑一个结点$u$,我们得知其下每个子树的最优决策。之后我们考虑在$u$处权值若额外增加$1$,则所有子树中最贵的决策的次数就都会减少$1$。我们可以将子树中的所有决策合并,并将决策的费用通过chmin操作与$c_u$进行比较替换。

具体实现就是使用稀疏线段树。我们将最优决策按照费用大小存储在稀疏线段树中。

之后考虑如何合并孩子的决策,我们知道稀疏线段树的合并操作是取决于稀疏线段树的实际顶点数(每合并一次会删除一个顶点),因为我们可以认为这部分的时间的摊还是$O(1)$,可以忽略。

最后如何将$t_u$加入,由于$u$的所有孩子$v$的前缀和$P_v$是相同的,因此我们可以让决策以$P_v+1$为开始下标排放在线段树中。

最后考虑chmin操作的实现,由于稀疏线段树中的权值是按照从大到小放置,因此可以二分,在线段树上的二分是$O(\log_2n)$。之后chmin操作就变成了区间覆写操作。

最后总的时间复杂度和空间复杂度均为$O(n\log_2n)$。

一类最小费用递增序列问题

题目1:给定一个长度为$n$的序列$a_1,\ldots,a_n$,要求找到另外一个非严格递增序列$b_1,\ldots,b_n$,定义$b$的费用为$cost(b)=\sum_{i=1}^n|b_i-a_i|$。仅要求输出最小的费用。其中$1\leq n\leq 10^6$,$0\leq a_i\leq 10^9$。

提供几道题目。

第一种,记$f_i(x)$表示递增序列$b_1,\ldots,b_i$其中$b_i=x$的最小费用$\sum_{j=1}^i|a_j-b_j|$。可以发现$f_i(x)=|x-a_i|+\min_{1\leq j\leq x}f_{i-1}(j)$,时间复杂度为$O(nm)$,其中$m$为值域大小。问题中值域比较大,但是可以发现,我们仅考虑$b_i\in a$,依旧可以找到费用最小的$b$。因此我们可以将时间复杂度优化到$O(n^2)$。

上面这种做法实际上已经是动态规划的极限了,我们无法再度优化。

可以考虑另外一种做法。记录$g_i(x)=\min_{j\leq x}f_i(j)$。可以发现$g_i$是一个递减函数,且$g_i$在任意点斜率非正,且斜率递增。记$opt(i)$是$g_i$的最小的坐标,满足$g_i(opt(i))=0$。

我们实际上可以将$g_i$理解为分段线性函数,而段是有限的,我们有能力维护所有斜率不同的段。同时段的开始和结束端点都是$a$的元素。

可以理解$g_0$为一条$y=0$的直线,下面我们考虑从$g_{i-1}$到$g_i$的转移。其实际上是将$x\leq a_i$的直线斜率减少$1$,而$x\geq a_i$的直线斜率增加$1$。修改后,我们还需要将斜率超过$0$的直线斜率修正回$0$。

下面来考虑两种情况:

  • $a_i\geq opt(i-1)$:这时候一定有$f_i(opt(i))=f_{i-1}(opt(i-1))$。
  • $a_i\lt opt(i-1)$:这时候一定有$f_i(opt(i))=f_{i-1}(opt(i-1))+opt(i-1)-a_i$。这是因为$f_{i-1}$在$opt(i-1)$左侧的斜率是小于$0$的整数。

我们可以发现无论是那种情况都有$f_i(opt(i))=f_{i-1}(opt(i-1))+t_i$的形式,而我们要求的是$f_n(opt(n))$,因此根据递推公式可以得出:$f_n(opt(n))=t_1+t_2+\ldots+t_n$。因此我们只需要计算$t_1,\ldots,t_n$即可。这允许我们仅关心这些直线的斜率,而不需要讨论直线的高度。

我们可以用线段数来维护斜率,记$d_i$表示点$i$到$i+1$之间的直线的斜率,假设我们已经用线段数维护了$g_{i-1}$。之后要计算$g_i$,其等价于区间的左侧$-1$,右侧$+1$,之后对大于$0$的部分斜率要调整到$0$(这个可以在线段树上二分,之后区间赋值即可)。而$t_i$可以在过程中计算。因此每次转化的时间复杂度为$O(\log_2n)$,总的时间复杂度为$O(n\log_2n)$。

上面的这种做法需要用到线段树,代码行数大概为$100$行左右。下面讲一种行数在$10$行以内的非常简单的做法,时间复杂度也是$O(n\log_2n)$。

我们可以不必维护整个线段树中每个$d_i$,我们仅维护每个那些满足$d_i>d_{i-1}$的位置$i$信息。我们维护一个多重集合$S$,如果$i$出现在$S$中,则表示以$d_i$为左端点的直线的斜率为$S$中严格大于$i$的元素的数目。在仅考虑$g_0$的时候,$S={-\infty}$。接下来考虑两种情况。

  • $a_i\geq opt(i-1)$:这时候$opt(i)=a_i$,因此我们将一个$a_i$加入到$S$中。
  • $a_i\lt opt(i-1)$:这时候$opt(i-1)$的斜率会增大为$1$,因此我们需要从$S$中删除一个$opt(i-1)$。同时为了保证$a_i$左侧的点的斜率减少$1$,我们需要加入两个$a_i$到$S$中。

上面这个做法写成代码非常简单:

cost = 0;
S = {-inf};
for(int i = 1; i <= n; i++){
    S = S + a[i];
    cost += max(S) - a[i];
    S = S - max(S);
    S = S + a[i];
}

题目2:给定一个长度为$n$的序列$a_1,\ldots,a_n$。我们可以以费用$I_j$将$a_j$增大$1$,以费用$D_j$将$a_j$减少$1$。要求输出最小的费用和方案。其中$1\leq n\leq 10^3$,$0\leq a_i\leq 10^9$。

我们将每段路都映射为网络流中的两个顶点,第i段路,对应两个顶点$L_i$,$R_i$。我们如何保证第i个路的海拔一定不高于第i+1个呢?我们从源点向$L_i$连流量为$a_i$费用为$0$的边,从$R_{i+1}$向汇点连流量为$a_{i+1}$费用为$0$的边,同时我们从$L_i$向$R_{i+1}$连一条容量为$a_i$,费用为$0$的路径。这样要做到最大流必定会导致流经$R_{i+1}$的流超过$a_i$。

那么我们可以增大一条路的海拔又怎么实现呢,我们从$R_i$到$L_i$连容量为无穷费用为$I_i$的边。而至于减少一条路的海拔,我们可以从$L_i$到$R_i$连容量为$a_i$费用为$D_i$的边。

最后$R_1$和$L_N$需要与汇点相连。

跑出最小费用最大流后,最小费用就是结果。

简单的规律题

题目:给定$n$,我们使用贪心算法,如果$n$非$0$,则找到最大的正整数$x$,满足$x^3\leq n$,之后将$n$减去$x^3$。最后我们可以的得到$n=x_1^3+x_2^3+\ldots+x_k^3$,我们记$f(n)=k$。现在给定$m$,要求计算$C=\max_{i=1}^nf(i)$,并输出$M=\max_{1\leq i\leq n, f(i)=C} i$。其中$m\leq 10^{16}$。

提供一道题目

首先我们考虑怎么计算$C$。我们可以发现如果我从小到大选择的是$x_1,\ldots,x_C$,那么对于所有$i$,都必定有$x_1^3+x_2^3+\ldots+x_i^3\lt (x_{i}+1)^3$。

下面我们提供一个贪心算法计算$C$。我们可以发现,如果存在一个更小的$x_{i-1}\leq y\lt x_i$,且$x_1^3+x_2^3+\ldots+x_{i-1}^3+y^3\lt (y+1)^3$,那么我们可以用$y$替换$x_i$。因此我们得到了一个贪心算法,每次都选择最小的$x_i$。

用上面的算法计算一下,会发现有$C\leq 20$。

接下来我们来考虑怎么计算$M$。这个比较麻烦,记$y$为最大的正整数,满足$y^3\leq M$。那么可以证明$x_C=y$或$x_C=y-1$。

考虑三种情况:

  • $x_C=y$的时候,此时$m_2\leq m-y^3$
  • $x_C\leq y-1$的时候,此时$m_2\leq y^3-1-(y-1)^3$

对于第二种情况,由于我们希望让$m_2$尽可能大,同时由于$y^3$的斜率是单调增的,因此我们在$x_C=y-1$的时候$m_2$可以取到最大。

上面这个算法我们直接递归执行,时间复杂度为$2^C$,是可以接受的。

实际上如果我们将$x^3$替换为$x^k$,问题也是可以通过同样的算法解决的。

参考资料