一些贪心问题

Published: by Creative Commons Licence

  • Tags:

前缀匹配问题

考虑下面问题:

形态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$,问题也是可以通过同样的算法解决的。

一类序列消除问题

问题1:给定一个长度为$n$的序列,你允许操作每次删除序列的某个元素,或者一次性删除两个序列中相邻的不同的元素,问最少需要执行多少次操作,可以将序列变为空。

记$c_i$表示元素$i$的出现次数,很显然我们每次每种元素最多消除一个,因此执行次数的下限为$\max_{i}c_i$。同时如果没有任何一个元素出现次数超过一半,那么我们可以贪心的每次选择出现次数最多的元素和另外一个相邻的不同元素进行消除,这样我们就能每次消除两个元素,因此给出了一个$\lceil \frac{n}{2} \rceil$的方案。

结合上面的分析,最少次数应该为$\max(\lceil \frac{n}{2} \rceil, \max_{i}c_i)$。

问题2:给定一个长度为$n$的序列$a$,你允许操作每次删除一段漂亮子序列,问最少需要执行多少次操作,可以将序列变为空,并给出方案。一段序列$s$是漂亮序列,当且仅当序列中相邻元素都不相同,即对于任意$i$,有$s_i\neq s_{i+1}$。

我们这里要将问题做一个转换,我们构建另外一个序列$b$,对于每个$a$中相邻的两个相同元素,我们在$b$中就加入一个对应的元素,比如$a=112223$,其转换后变成$b=122$。这时候你会发现从$a$中删除一个漂亮序列,对应的就会从$b$中删除一个元素或者删除两个相邻元素,同理$b$中的删除一个元素或删除两个相邻元素对应于$a$中删除一个漂亮序列。换言之,就是我们现在需要做的就是在$b$中每次删除一个元素或删除两个相邻元素,并使之为空。这实际上就是问题1考察的,我们记结果为$r$,那么现在$b$删除为空了,对应的$a$只剩下一个漂亮序列,因此答案是$r+1$。

那么怎么求出方案呢,这里我们可以用一些平衡树维护每个字符的出现位置,用线段树记录删除位置,加上贪心算法和并查集,时间复杂度可以约束在$O(n\log_2n)$。

提供一道CF题目

问题3:给定一个长度为$n$的序列$a_1,\ldots,a_n$。我们每次可以执行这样的操作:选择两个序列中相邻的元素$x,y$,将两个数替换为$x+2y$。重复这个操作直到最后剩下一个数,问剩下的数最大是多大,记这个数为$f(a_1,\ldots,a_n)$。这个问题要求回答$q$次询问,每次询问给定$l,r$,要求求出$f(a_l,\ldots,a_r)$。这里$n,q\leq 10^5,|a_i|\leq 10^9$

我们先简化一下问题,如果替换后的数为$x+y$怎么解决?这个很简单,我们发现总和永远不会改变,因此维护一个前缀和就可以$O(1)$求解每个请求了。

再在原来的基础上增强一点,如果$a_i$始终非负如何。我们发现最终的数是每个数乘上一个系数之后加总得到的,第$i$个数能乘的最大的系数为$2^{i-1}$。因此我们可以不断选择尾部的两个元素进行替换,这样可以得到最大值$\sum_{i=1}^n2^{i-1}a_i$。那么对于多请求下,我们可以维护前缀和$g(k)=\sum_{i=1}^n2^{i-1}a_i$,之后区间$[l,r]$的最大值为$2^{-l}(g(r)-g(l-1))$。通过预处理,也可以$O(1)$处理每个请求。

好的,现在回到这个问题中来。我们从后往前处理。可以发现,对于第$i$个数,我们如果选择将其先与前面的数进行合并再与后面的数合并,就相当于后缀每个数不变,但是如果和前面的数进行合并后再和前面的数合并,那么就相当于让后缀每个数乘上2。如果后缀非负,那么我们自然希望它乘上2,否则希望它不变。这提供了一个贪心思路,我们不断从后向前处理,如果发现后缀是负数,则只乘2,同时将后缀和清0(因为会先合并所有前面的数在搞它),否则乘上2。

我们可以预先处理出每个下标$j$,最大的下标$i$,满足$i<j$且$g(j)-g(i-1)<0$。之后我们发现这些下标将整个序列分成若干个不相交的块,在上面搞个倍增就可以$O(\log_2n)$处理每个请求了。

问题4:给定$n$种颜色的史莱姆,第$i$种颜色的史莱姆数量为$a_i$。现在我们每次可以选择两只不同颜色的史莱姆,将它们消灭。问重复上面操作,是否最后可以消灭所有史莱姆。

直接给结论,记$m=\sum_{i}a_i$,则能完成目标当且仅当$m$是偶数,且$\forall 1\leq i\leq n(a_i\leq \frac{m}{2})$。

偶数的要求非常显然,而第二个要求的必要性也很显然,下面在$m$是偶数的前提下我们来证明第二个要求的充分性。

通过归纳法证明。当$m=0$的时候命题显然成立。现在假设当$m\leq 2k-2$的时候命题均成立,接着考虑$m=2k$的时候。我们可以将$a_i$从大到小排序,之后将$a_1$和$a_2$减少$1$。

新的情况共有$m-2$只史莱姆,很显然是偶数。同时有$a_1\leq \frac{m}{2}\Rightarrow a_1-1\leq \frac{m-2}{2}$,对于$a_2$也是同理。而对于$a_3$,一定有$a_3\leq \frac{m}{2}-1\leq \frac{m-2}{2}$,因此新的情况满足$\forall 1\leq i\leq n(a_i\leq \frac{m-2}{2})$。

其实这个问题我们可以修改为只能删除两只相邻的史莱姆,答案也是成立的。

参考资料