一些贪心问题

Published: October 28, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• table

前缀匹配问题

考虑下面问题：

形态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$。

提供几道题目。

• https://codeforces.com/contest/713/problem/C
• https://darkbzoj.tk/problem/1367

第一种，记$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)$处理每个请求了。

每次从$k$组中各选一个元素删除

给定$n$种颜色的史莱姆，第$i$种颜色的史莱姆数量为$a_i$，总数为$m$。现在我们每次可以选择$k$只不同颜色的史莱姆，将它们消灭。问重复上面操作，最多能执行多少次上面的删除操作。其中$k$能整除$m$

首先我们考虑出现次数最多的颜色数量，记为$x$。如果$kx\leq n$，那么我们可以每次贪心选择出现次数最多的$k$种颜色删除。可以证明这样最多删除次数为$\left\lfloor \frac{n}{k}\right\rfloor$。下面提供证明：

考虑我们已经按照出现次数从大到小对颜色进行排序，即$a_1\geq a_2\geq \ldots \geq a_n$。我们选择$a_1,\ldots,a_k$进行操作。如果$a_1>a_{k+1}$，删除完成后可以得到$k(a_1-1)\leq n-k$以及$ka_{k+1}\leq k(a_1-1)\leq n-k$，即操作完成后序列依旧满足所有分组比例不超过$\frac{1}{k}$。另外情况就是$a_1=a_{k+1}$，这时候可以发现之后每次删除都满足$a_1-a_{k+1}\leq 1$（每次删除前都要重新排序）。由于始终满足$a_k-1\geq a_{k+1}-1$，因此在最后一次删除发生的时候，$a_{k}-1=0$，故$a_{k+1}\leq 1$，$a_1-1,\ldots,a_{k-1}-1\leq 1$。换言之，现在每组最多只有一个元素，由于删除不能再发生了，可知目前元素总和为$n\pmod k$。显然总的删除次数为$\left\lfloor \frac{n}{k}\right\rfloor$。

之后考虑另外一种情况，此时$kx>n$。这时候比较特殊，我们每次都可以从$a_1$中删除$1$，因此总删除次数取决于$a_2,\ldots,a_n$，即我们现在有$n-1$种颜色的分组，每次选择$k-1$个删除，问最多可以执行多少次删除。这是一个规模更小的子问题。

一个简单的算法就是将$a$进行排序，之后找到第一个满足$(k-i+1)a_i\leq \sum_{j=i}^na_j$的$i$，答案为$\left\lfloor \frac{\sum_{j=i}^na_j}{k-i+1} \right\rfloor$。

广告投放问题

题目1：现在有$n$个广告，第$i$个广告需要投放$a_i$次。同时有$m$个观众，第$i$个观众可以看$b_i$个广告。同时不能将同种广告多次投放给同一个用户（否则用户会感到无聊）。问是否存在一种投放策略，能使得所有广告得到投放。

等价问题：有$n$种颜色的球，第$i$种颜色的球有$a_i$个。同时有$m$个容器，第$i$个容器中可以放入$b_i$个球。每个容器中放入的球的颜色必须不同。问是否能将所有球放入容器中。

其中$1\leq n,m\leq 10^6$，$1\leq a_i,b_i\leq 10^9$。

提供一道题目。下面的解法来自这道题的官方题解。

很显然我们可以建模网络流来求解，为每种颜色的球建立顶点，同时为每个容器建立顶点。每种颜色的球和每个容器之间连一条容量为$1$的边。如果最大流正好为$\sum_{i=1}^na_i$，那么就有解。

当然我们不可能真的去跑这么大的一个网络。我们可以考虑最大流的对偶问题，最小割。不失一般性，我们认为$a$是递减排序的。记$A\subseteq [n]$和$B\subseteq [m]$表示最小割下与源点相连的球顶点和容器顶点的下标。那么最小割自然为

$$\sum_{i\notin A} a_i+\sum_{i\in B}b_i+|A|(m-|B|)$$

我们记$k=|A|$，那么这时候很显然最小割为：

$$\begin{aligned} &\sum_{i=k+1}^n a_i+\sum_{i\in B}b_i+k(m-|B|)\\ =&\sum_{i=k+1}^n a_i+\sum_{i\in B}b_i+\sum_{i\notin B}k \end{aligned}$$

这时候由于是最小割，而$B$的选择是独立的，因此上面的公式可以简化为下面形式：

$$\sum_{i=k+1}^n a_i+\sum_{i=1}^m\min(b_i,k)$$

同时考虑到$k$可以在$0$到$n$中任意选择，因此存在方案的前提是

$$\begin{aligned} &\forall k\in[0,n](\sum_{i=k+1}^n a_i+\sum_{i=1}^m\min(b_i,k)\geq \sum_{i=1}^na_i)\\ \Rightarrow& \forall k\in [0,n](\sum_{i=1}^m\min(b_i,k)\geq \sum_{i=1}^ka_i) \end{aligned}$$

因此我们得到了解存在的充要条件。可以通过预处理后线性求解。时间复杂度为$O(n\log_2n+m)$。

贪心和费用流

费用流中按照最小费用路径增广的思路实际上也是一种贪心，并且由于费用流存在已知的理论基础，因此我们很多时候可以通过模拟费用流直接解决一些组合优化问题，而不需要重头开始证明一个新的算法。

考虑下面几个问题：

给定$n$件商品，其中第$i$件商品的原价是$p_i$，优惠后的价格是$d_i$，我们现在手头上有$k$张优化券，以及金币$m$。我们希望买到尽可能多的商品，问如何购买以及最多的商品数量。

这个问题实际很难考虑并证明出一个贪心算法。一个简单的方案是二分商品数目，对于给定的买入商品数$x$，计算买入的最小费用$f(x)$。这里最小费用可以用WQS二分来计算，这样的话时间复杂度为$O(Tn\log_2n)$，$T$是WQS二分次数，一般为$60$。

上面这个算法比较慢，但是容易实现并且验证正确性。

还有一个思路就是设计一个费用流。每个商品建立一个顶点，同时优化券和原价建立对应的两个顶点。之后一直根据最小费用路径进行增广，直到费用总和超过$m$。

但是费用流的时间复杂度更加大，这里是不可取的。但是可以发现费用流中，增广路只有三种，一种是直接跑优化券，一种跑原价，还有一种就是将原本某个使用优惠券的商品替换为使用原价，而新商品使用优惠券（如果存在更长的增广路，比如从原本使用优惠券的商品中选择两个替换，这样就意味着原来的费用流中存在负环，但是这是不可能的）。

上面的流程费用流跑起来很慢，但是我们可以手动进行实现。实现方法就是维护两个最小堆，一开始包含所有商品，第一个堆$A$中按照原价排序，第二个堆$B$中按照优惠价排序。同时我们维护一个最小堆$C$，其中存储使用优惠券的商品，它按照优惠力度排序（即$p_i-d_i$）。

之后我们每次选择增广费用最小的路径进行增广。实现方式就是记$a$为$A$种堆头，同理$b,c$分别是$B$和$C$的堆头，使用$a$的增广费用为$p_a$，而使用$b$的增广费用分成两种情况讨论，如果$C$的大小为$k$，则增广费用为$d_b+p_c-d_c$，否则增广费用为$d_b$。选择最小的增广即可。

双流水线调度算法

考虑一个工厂，共需要生产$n$个零件。每个零件需要经过两个流水线打磨。第一个流水线处理第$i$个零件的时间为$a_i$，第二个流水线处理第$i$个零件的时间为$b_i$。每个流水线只有一台机器，因此一次性只能同时处理一个零件，且每个零件必须依次经过流水线一和流水线二的加工。并且如果某个零件比另外一个零件先经过流水线一的处理，那么前者必须比后者先经过流水线二的处理。现在允许任意排列零件的处理顺序，要求计算最小花费的时间。

这里需要使用Jhonson算法来解决这个问题。

我们记$T(N,t)$表示要求加工$N$中的所有零件，但是$t$时后第二个流水线才就绪，所需要的最少时间。

很显然$T(N,t)=\min_{i\in N} T(N-i,b_i+\max(t-a_i,0))$。

现在考虑在状况$T(N,t)$时，最优情况下会先加工零件$i$，再加工零件$j$。此时$T(N,t)=T(N-i-j,b_j+\max(b_i+\max(t-a_i,0)-a_j,0))$。对于右边的式子稍微进行化简：

$$\begin{aligned} &b_j+\max(b_i+\max(t-a_i,0)-a_j,0)\\ =&b_j+b_i-a_j+\max(\max(t-a_i,0),a_j-b_i)\\ =&b_j+b_i-a_j+\max(0,t-a_i,a_j-b_i)\\ =&b_j+b_i-a_j-a_i+\max(a_i,t,a_j-b_i+a_i) \end{aligned}$$

由于交换$i,j$顺序不会优化结果，因此可以推出不等式

$$b_j+b_i-a_j-a_i+\max(a_i,t,a_j-b_i+a_i)\leq b_i+b_j-a_i-a_j+\max(a_j,t,a_i-b_j+a_j)$$

减去两边的公共项，得到：

$$\max(a_i,t,a_j-b_i+a_i)\leq \max(a_j,t,a_i-b_j+a_j)$$

很显然如果$\max(a_i,a_j-b_i+a_i)\leq \max(a_j,a_i-b_j+a_j)$是上面的公式的充分条件。该式稍作转换可以得到：

$$\max(-a_j,-b_i)\leq \max(-a_i,-b_j)$$

即

$$\min(a_j,b_i)\geq \min(a_i,b_j)$$

上面的比较关系显然满足自反性，但是却不满足传递性，因此不能拿来直接排序。实际上考虑这样的三个二元组 (1,0),(0,0),(0,1)，可以发现它们破坏了传递性。因此这个不等式实际上不能直接用来排序。

有另外一种方式可以解决这个问题。我们把任务分成两类，第一类是$a_i>b_i$的任务集合，而第二类是$a_i\leq b_i$的任务集合。我们先按$a_i$从小到大处理第一类任务，之后按照$b_i$从大到小处理第二类任务。实际上不难发现这样的操作序列满足了对于$i\lt j$有$\min(a_j,b_i)\geq \min(a_i,b_j)$成立，因此这就是一个手动合成的最优序列。

提供一道题目。

田忌赛马

两个团队进行PK，每个团队有$n$个人，第一个团队成员的能力从小到大分别为$A_1,\ldots,A_n$，第二个团队成员的能力从小到大分别为$B_1,\ldots,B_n$。现在我们要对第一个团队中的成员进行排列，之后让两个团队中的成员进行一对一厮杀，比赛的结果由能力高的胜出，如果能力相同视作平局。胜利方加一分，失败方扣一分，平局双方都不加分。现在问第一队最多和最少能拿到多少分。其中$1\leq n\leq 10^6$

提供一道题目

由于双方总分为0，因此要让第一个团队分最低，等价于让第二个团队分最高，因此问题只有一个，给定两个团队，要求计算第一个团队的最高可能得分。

很显然这是一个最大权二分图匹配问题，但是数据范围太大。因此我们需要更多的观察。

我们不妨考虑几种情况

1. $A_1>B_1$，则至少有一个最优解中，$A_1$与$B_1$进行比赛。

如果最优解中$A_1$与$B_i$比赛，而$B_1$与$A_j$比赛，则这两场比赛的分数为$s(A_1-B_i)+s(A_j-B_1)=s(A_1-B_i)+1$。而考虑交换$A_1$与$A_j$的对手得到的分数为$s(A_1-B_1)+s(A_j-B_i)=s(A_j-B_i)+1\geq s(A_1-B_i)+1$。因此我们可以一个新的最优解，其中$A_1$与$B_1$进行比赛。

1. $A_n>B_n$，则至少有一个最优解中，$A_n$与$B_n$进行比赛。

如果最优解中$A_n$与$B_i$比赛，而$A_j$与$B_n$比赛，则两场比赛得分为$1+s(A_j-B_n)$，考虑交换$A_n$与$A_j$的对手后得分为$1+s(A_j-B_i)\geq 1+s(A_j-B_n)$，因此我们可以得到一个新的最优解，其中$A_n$与$B_n$进行比赛。

1. 在上面两个条件都不满足的前提下，则至少存在一个最优解，使得$A_1$与$B_n$进行比赛。

此时有$A_1\leq B_1$和$A_n\leq B_n$。考虑最优解中$A_1$与$B_i$进行比赛，而$A_j$与$B_n$进行比赛，且$A_1<A_j$，则两场比赛得分有$s(A_1-B_i)+s(A_j-B_n)$，交换$A_1$和$A_j$的对手后得分为$s(A_1-B_n)+s(A_j-B_i)$。分几种情况讨论

3.1. 如果$A_j<B_n$，则$s(A_1-B_n)+s(A_j-B_i)=s(A_j-B_i)\geq s(A_1-B_i)=s(A_1-B_i)+s(A_j-B_n)$

3.2. 如果$A_j=B_n$，则$s(A_1-B_n)+s(A_j-B_i)=s(A_j-B_i)-1=s(A_1-B_i)=s(A_1-B_i)+s(A_j-B_n)$

因此无论哪种情况下，新的得分都不小于原来得分，即至少存在一个最优解，使得$A_1$与$B_n$进行比赛。

现在我们得到了一个算法，枚举所有情况并贪心选择比赛策略。时间复杂度为$O(n)$。

参考资料

• 浅谈双流水线调度问题以及Jhonson算法