贪心还能这么玩？——浅谈进阶贪心

· · 个人记录

前言

贪心，是一种很玄学的算法，入门的贪心十分简单，但也有一些非常有意思的贪心。本文将会介绍一些略微进阶的贪心——邻项交换法、哈夫曼编码、后悔贪心，主要通过例题讲解的方式来带大家领略贪心思想。由于本人才疏学浅，所涉内容也较为浅显，更多起的是抛砖引玉的作用。

邻项交换法

一、简介

邻项交换法是求解排序贪心中常见的方法，具体指在求解整个序列的最优解时，只考虑两个相邻的元素，对其位置进行交换，比较交换前后对答案优劣的影响，构造不等式，由此推广得到整个序列最优解的排序方法。

二、排列贪心

排列贪心是贪心的常见题型。满足以下特征：

  1. 给你一个序列，要求对其进行排序后按题目要求模拟后求出最优解。

  2. 序列的排序规则 难以确定（也就说一眼看过去不知道按照什么进行排列）。

当然也不一定，因为也有可能是 dp，还是要根据具体题目进行分析。

三、严格弱序

  1. 引入

    严格弱序（Strict Weak Ordering），是 C++ 排序算法 中的一个重要概念，也是邻项交换法思想的 基石，因此在正式开讲前，有必要介绍一下。

    在学习中，我们常会对一些东西进行排序。对于大多数情况，我们可以直接用 C++ 自带的 sort 函数（默认 升序 排列，即从小到大）。但当我们需要 降序 排列，或是要对 结构体 进行排列时，就需要自己写一个 比较规则（可以 重载运算符，也可以编写 比较函数）。但并不是什么比较规则都是可行的，比较函数一定要满足 严格弱序。

  2. 定义

    严格弱序 一般指集合 S 的 二元关系 <（注意，这里的 < 并不是我们平常认为的小于号，它只是一个关系，可以是任意重载后的运算符），它满足以下条件：

    • 非自反性：对于所有 x\in S，均不满足 x<x。

    • 非对称性：对于所有 x,y\in S，若满足 x<y，则不满足 y<x。

    • 传递性：对于所有 x,y,z\in S，若满足 x<y，y<z，则满足 x<z。

    • 不可比性的传递性：对于所有 x,y,z\in S，若 x 与 y 不可比（若 x < y 与 y < x 均不满足，则 x 与 y 不可比），且 y 与 z 不可比，则 x 与 z 不可比。

  3. 理解

    显然 \leq 和 \geq 并不满足严格弱序，因为对于 x\in S，有 x \leq x，不满足 非自反性。\geq 同理。

    C++ 中的排序都是完全按照严格弱序进行的，若你编写的比较规则不满足严格弱序，那么将会出现意想不到的错误。

    在排序贪心中，严格弱序的 传递性 异常重要。因为我们在求解中正是先通过对于相邻两项的研究推广出整个序列的排序方法，而这正是因为严格弱序的 传递性 才保证了正确性。

    严格弱序在邻项交换法的更多运用在下面会更深入的讲解。

四、流程

邻项交换法流程基本如下：

  1. 先考虑只有两个元素时的答案 ans_1；

  2. 将两个元素交换位置后，得到新的答案 ans_2；

  3. 比较 ans_1 和 ans_2，根据题目列出不等式。

  4. 得出整个序列的排序方法。

五、例题

P1080 [NOIP2012 提高组] 国王游戏

经典老题，我每年都讲，太经典了。

题意：

有一个序列，序列中每个元素都有两个权值 a 和 b，每个元素最终的值等于排在该元素前所有元素 a 的乘积除以该元素自己的 b 的值。要求你对该序列进行排列后，最终序列中最大的元素值最小。

思路：

首先本题很明显是一道 排列贪心，接下来会详细地讲解邻项交换法的 原理 和 流程。

既然是一道排序贪心，那么最关键的问题是按照什么进行排序。对于整个序列我们难以下手，那么可以先考虑 特殊情况，只研究 两个相邻元素 的 不同排列 对答案的影响，再从中发现规律，推广到整个序列的排序方法。而这，正是邻项交换法的 思想核心——从局部到整体。

具体到本题，我们先只考虑两个元素，元素 A 的权值分别为 a_1 和 b_1，元素 B 的权值分别为 a_2 和 b_2，这两个元素前面所有元素权值 a 的乘积为 a_0。假设 A 在前面。如表：

元素 left right
前面的 a_0
A a_1 b_1
B a_2 b_2

按照题意可得 ans_1=\max(\frac{a_0}{b_1},\frac{a_0 \times a_1}{b_2})。

按照 邻项交换法 的流程，接下来我们需要 将 B 与 A 交换位置，比较交换前后答案孰优孰劣。如表：

元素 left right
前面的 a_0
B a_2 b_2
A a_1 b_1

可得 ans_2=\max(\frac{a_0}{b_2},\frac{a_0 \times a_2}{b_1})。

接下来比较 ans_1 和 ans_2 的大小。首先显然

\frac{a_0 \times a_1}{b_2}>\frac{a_0}{b_2},\frac{a_0 \times a_2}{b_1}>\frac{a_0}{b_1}

我们假设 ans_1<ans_2，即

\max(\frac{a_0}{b_1},\frac{a_0 \times a_1}{b_2})<\max(\frac{a_0}{b_2},\frac{a_0 \times a_2}{b_1})

那么可证

\frac{a_0 \times a_1}{b_2}<\frac{a_0 \times a_2}{b_1}

变形可得

a_1 \times b_1 < a_2 \times b_2

因此当 a_1\times b_1<a_2\times b_2 时，我们可以得到 ans_1<ans_2 的结论。而我们要求的是最大值的最小值，为了使 ans 取到最小值，只需将每个元素按 a\times b 从小到大排序即可。

本题还需要高精，不在本文论述范围内，就不说了。

小结：

上面我们通过邻项交换法，只考虑两个相邻元素交换位置前后的不同结果，得出最优的排列方式，根据严格弱序的 传递性，推广到整个序列，得出答案。这就是邻项交换法的基本流程。

P1248 加工生产调度

经典老题，我每年都讲，太经典了。

题意：

有 n 个产品，每个产品分别在 A、B 两个车间进行加工，且必须现在 A 车间加工再在 B 车间加工。产品 i 在 A、B 车间加工分别需要 a_i、b_i 分钟。问：如何安排 n 个物品的加工顺序，使总加工时间最短。

思路：

同样是一道排序贪心，我们还是思考该怎么进行排序。

按照 邻项交换法 的流程，我们先考虑只有两个产品的情况。设第一个产品在 A、B 加工的时间分别为 a_1、b_1，第二个产品在 A、B 车间加工的时间分别为 a_2、b_2。假设先加工第一个，再加工第二个。如表：

产品 在 A 车间加工时间 在 B 车间加工时间
第一个 a_1 b_1
第二个 a_2 b_2

可得加工完成最短时间也就是加工完第二个产品的时间，即 ans_1=a_1+\max(b_1,a_2)+b_2。

接下来 将两个产品加工顺序反一下。如表：

产品 在 A 车间加工时间 在 B 车间加工时间
第二个 a_2 b_2
第一个 a_1 b_1

可得加工完成最短时间也就是加工完第一个产品的时间，即 ans_2=a_2+\max(b_2,a_1)+b_1。

我们假设 ans_1<ans_2，所以

a_1+\max(b_1,a_2)+b_2<a_2+\max(b_2,a_1)+b_1

移项得

\max(b_1,a_2)-a_2-b_1<\max(b_2,a_1)-b_2-a_1

因为两边相当于消去较大的那个数，留下较小的那个数的相反数，即

-\min(b_1,a_2)<-\min(a_1,b_2)

两边同乘以 -1，得

\min(a_1,b_2)<\min(a_2,b_1)

因此若 \min(a_1,b_2)<\min(a_2,b_1)，则 ans_1<ans_2。而我们要求最短时间，因此按 \min(a_1,b_2)<\min(a_2,b_1) 对原序列进行排序即可。

小结：

不，还没有结束！还记得一开始我们介绍的 严格弱序 吗，我们编写的 比较规则 一定要满足严格弱序。那么我们刚才得出的比较规则满足严格弱序吗？很可惜，并没有。该比较规则未满足严格弱序中的 不可比的传递性（忘记的同学拉到最上面再看一下）。

比如说有

x.a=11, \ \ \ \ \ \ \ \ \ x.b=45; y.a=6, \ \ \ \ \ \ \ \ \ y.b=6; z.a=19, \ \ \ \ \ \ \ \ \ z.b=81

那么对这三个元素按上述的比较规则进行排序。比较元素 x 和 y：因为 \min(x.a,y.b)=6,\min(x.b,y.a)=6，x <y 与 y<x 均不满足，即 x 与 y 不可比；比较元素 y 与 z：因为 \min(y.a,z.b)=6,\min(y.b,z.a)=6，y <z 与 z<y 均不满足，即 y 与 z 不可比；比较元素 x 与 z：因为 \min(x.a,z.b)=11,\min(x.b,z.a)=19，满足 x < z，即 x 与 z 可比。

综上所述，\min(a_1,b_2)<\min(a_2,b_1) 不满足严格弱序中的 不可比的传递性，这个比较规则也就伪了，因此我们需要设计一个满足严格弱序的比较规则。那么如何设计呢？可以发现，因为最终答案与 a 相加和的大小相关，所以当两个产品的 \min 值相等时 a 值小的在前面会答案会更优。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e4+7;
int n,t;
ll ans,sum;
struct node
{
    int a,b,id;

    bool operator < (const node & x) const
    {
        if(min(b,x.a)==min(a,x.b))
            return a<x.a;
        return min(a,x.b)<min(b,x.a);
     } 
}s[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i].a);
    for(int i=1;i<=n;i++)
        scanf("%d",&s[i].b),s[i].id=i;  

    sort(s+1,s+1+n);

    sum=ans=0;
    for(int i=1;i<=n;i++)
    {
        sum+=s[i].a;
        ans=max(ans,sum)+s[i].b;
    }

    printf("%lld\n",ans);
    for(int i=1;i<=n;i++)
        printf("%d ",s[i].id); 

    return 0;
}

真正的小结：

本题仍然是邻项交换法的应用，不过本题还需要保证 设计的比较规则满足严格弱序，这是我们在使用邻项交换法的时候一定要注意的一点，一不小心就会写出错误的比较规则。一般来说，像加减乘除等运算会满足严格弱序，但像 \min,\max 等运算可能会不满足严格弱序，需要注意。

其他例题：

P2123 皇后游戏（与加工生产调度类似）

哈夫曼编码

一、引入

假设我们现在有一份文件，其中只有三个字符：A，B，C，我们需要用 二进制编码 来准确的表达它们，且编码总长度最短（即 单个字符出现频率（即出现次数） \times 该字符编码长度 的累加和最短）。

字符 频率 编码
A 191 000
B 98 001
C 10 010

最终长度为 (191+98+10) \times 3=897。我们可以让编码总长度再短一些。

字符 频率 编码
A 191 0
B 98 101
C 10 100

最终长度为 191 \times 1+98 \times 3+10 \times 3=515。似乎还可以再短些？

字符 频率 编码
A 191 0
B 98 1
C 10 00

最终长度为 191 \times 1+98 \times 1+10 \times 2=309，确实更短了。但这样编码是错误的，因为其不能准确地表示每一个字符。因为当你收到形如 000 这样的编码时，你就懵了：是 3 个 A，还是 1 个 A 和 1 个 C 呢？不清楚。因为其中有字符的编码是另一个字符的编码的 前缀，而第二个表就没有这样的现象。而像这样的编码就称为 哈夫曼编码，下面开始正式讲解。

二、简介

哈夫曼编码是一种根据 字符出现频率 来构造满足 任意一个字符编码不是另一个字符编码的前缀 且 总编码长度最短 的编码方式，基于 树形结构 和 贪心 思想，由 哈夫曼树 来实现。

三、定义

这里给出一些专门词汇的定义，有助于对下文的理解。

  1. 路径

    在一棵树中，两个结点间的通路称为 路径。

  2. 路径长度

    在一棵树中，两个结点间的路径所经过的边的条数称为 路径长度。

  3. 结点的权

    根据题目要求所赋给结点的数值（在哈夫曼树中即为单个字符的 出现频率）称为 结点的权。

  4. 结点的带权路径长度

    从根节点到该结点间的路径长度与该结点的权的 乘积 称为 该结点的带权路径长度。

  5. 树的带权路径长度

    所有 叶子结点 的带权路径长度之和称为 树的带权路径长度，简称为 WPL。

  6. 哈夫曼树

    给定 n 个权值（这里则是字符出现频率）作为 n 个叶子节点，构造一棵二叉树，若该树的带权路径长度最小，则称这样的树为 哈夫曼树，也叫 最优二叉树。假设有序列 \{ 1,2,3,4,5\}，其哈夫曼树如图：

四、实现

之所以哈夫曼编码可以用哈夫曼树来实现，是基于一条定理：任何一个不是其他字符编码的前缀的字符的编码一定可以用一棵树（常见的是二叉树，但也可以是多叉树）来表示 。如字符 \{I,A,K,1,O,l\} 用哈夫曼树（二叉）表示：

根据从根节点到叶子结点的路径可以得到每个字符的编码：

字符 编码
I 111
A 110
K 10
1 01
O 001
l 000

生成的编码满足上述条件。

证明（感性认知）：对于哈夫曼树来说，每个字符对应的都是其 叶子结点，也只有其叶子结点才 有权值。从根结点到子结点的路径并没有 完全包含 关系，也就不可能出现一个字符的编码是另一个字符编码的前缀的情况了。

有了上面的定理之后，那么求哈夫曼编码也就转化为另一个问题：如何求出一棵最优的编码树，也就是哈夫曼树。

哈夫曼树的构建就用到了 贪心 的思想。

算法流程：

假设有四个字符，频率分别为 \{11,45,1,4\}，其构建哈夫曼树流程如下：

感性认知：按照上述的算法流程进行，最终 权值越大 的结点一定会离根结点 距离越小，相当于最后求权值时 （结点的权 \times 路径长度） 时大的数乘上了小的数，树的带权路径长度最小。

具体实现时可以使用 优先队列 进行。

五、例题

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

没错，合并果子事实上就是 二叉哈夫曼树 的实现，想必大家都会做，这里只是指明哈夫曼树的实现：使用 堆。

代码：

#include<bits/stdc++.h>
using namespace std;

int n,x,ans;
priority_queue<int,vector<int>,greater<int> >pq;

int main()
{    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x),pq.push(x);
    for(int i=1;i<=n-1;i++)
    {
        int a=pq.top();
        pq.pop();
        int b=pq.top();
        pq.pop();
        ans+=a+b;
        pq.push(a+b);
    }
    printf("%d",ans);
    return 0;
}

P2168 [NOI2015] 荷马史诗

题意：

求将 n 个单词用 k 进制编码，满足以下条件：任意一个单词的编码不是另一个字符编码的前缀；最后编码总长度最短。

思路：

在学了上面的内容之后，这一看不就是哈夫曼编码吗？但本题是 k 进制编码而不是二进制，也就是说本题是 多叉哈夫曼树。具体实现与二叉哈夫曼树差不多，每次从树集合中选出 k 个最小权值子树合并。但要注意的是：最后一次合并时，子树个数可能会不足 k 个！这显然不是最优解。而要解决这个问题，我们需要在进行上述流程前，添加一些权值为 0 的叶子结点，使单结点子树的个数满足 (n-1) \bmod (k-1)=0。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node
{
    ll val,hei;

    bool operator < (const node & x) const
    {
        if(val==x.val)
            return x.hei<hei;
        return x.val<val; 
    }
};
priority_queue<node>q;
int n,k;
ll ans;

inline ll read()
{
    ll sum=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++)
    {
        ll x;
        x=read();
        q.push((node){x,1});
    }
    while((q.size()-1)%(k-1)!=0)
        q.push((node){0,1});

    while(q.size()>=k)
    {
        ll v=0,h=0;
        for(int i=1;i<=k;i++)
        {
            node now=q.top();
            q.pop();
            h=max(h,now.hei);
            v+=now.val;
        }
        ans+=v;
        q.push((node){v,h+1});
    }

    printf("%lld\n%lld",ans,q.top().hei-1);

    return 0;
}

六、总结

哈夫曼编码看似简单，但很多人（包括我）都对其了解不深，真正遇到题目连看都看不出来。因此在这里对哈夫曼树进行详细的讲解，希望对大家有所帮助。

后悔贪心

一、简介

贪心的缺点就是 鼠目寸光，拘泥于眼见的最佳选择，最终捡了芝麻丢了西瓜，反而不是最优的解法。而 后悔贪心 就是在普通贪心的基础上，有了可以后悔的操作，以此获取最优解。

二、例题

P2949 [USACO09OPEN]Work Scheduling G

题意：

有 n 个工作，给出每个工作 i 的截止时间 D_i 和 报酬 P_I，每个单位时间只能做一个工作。问能获得的最大利润是多少。

思路：

这是一道较为简单的后悔贪心。首先最贪心的想法是：截止时间最早的工作肯定要先做。但这显然是不一定的，可能做截止时间靠后的工作可能会获得更多的报酬。

因此我们加入一个 后悔 的操作：先将所有工作按截止时间从小到大排序；对于每一个工作，若有时间做就做（普通的贪心），将其价值加入 小根堆 中；若找到一个 没时间做 但 价值比堆顶大 的工作，就 后悔，用做原先工作的时间来做价值更高的工作（后悔贪心的操作），这样得到的总价值一定最优。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll read()
{
    ll sum=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int N=1e5+7;
struct node
{
    int time,val;

    bool operator <(const node&x)const
    {
        return time<x.time;
    }
}a[N];
int n;
ll ans;
priority_queue<ll,vector<ll>,greater<ll> >q;

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i].time=read(),a[i].val=read();

    sort(a+1,a+1+n);

    for(int i=1;i<=n;i++)
        if(a[i].time<=q.size())//没时间做
        {
            if(a[i].val>q.top())//如果价值比最小的那个价值大
            {       
                ans+=a[i].val-q.top();//后悔
                q.pop();
                q.push(a[i].val);
            }
        }   
        else//有时间做
        {
            ans+=a[i].val;
            q.push(a[i].val);
        }

    printf("%lld",ans);
    return 0;
 }

P1792 [国家集训队]种树

题意：

有 n 个种树的位置，形成一个 环，顺时针编号 1\sim n。每一个位置 i 都有一个美观值 a_i，在这里种树即可获得 a_i 的美观值。但是两棵树不能种在 相邻的位置（i 和 i+1 是相邻位置，1 和 n 也是相邻位置）。求种 m 棵树的最大的美观值是多少。

思路：

首先考虑普通的贪心是怎么做：若没有不能放相邻位置的约束条件，肯定是选美观值前 m 大的树。但加了这么个限制之后，这个贪心就伪了。

假如有四棵树 \{233,114,191,7\}。

贪心地选择最大的树 233，那么 191 和 114 都不能选了。

只能选择剩下中最大的 7。

这样的最终答案为 233+7=240。

但是若是选择 191 和 114，最终答案为 191+114=305，比原先贪心所得的解更优，说明原先的贪心是错的。

因此为了能够处理这样的问题，我们需要加入 后悔 的操作（也就是能够使我们 撤销上一步错误的贪心选择）。在这题中，一开始给每个点建立 双端链表，在取了当前的最大值之后，新加一个点，其权值等于 选的点的左边点的权值 + 选的点的右边点的权值 - 选的点的权值，同时其 新点左端更新为原左端的左端，右端更新为原右端的右端。为什么这么做呢？如图：

在选了最大的点 233 之后，答案为 233，同时加入新点 72 （191+114-233=72），同时新点的左端指向 7，新点的右端指向 7。

接下来再选最大的 191，可 191 已被标记，跳过。再接下来选 114，也被标记过了，跳过。然后是 72，可以选。

选了之后 7 不可选，由于选了两次，退出，最终答案是 233+72=305。

发现了吗，这个最终答案与选 191 和 114 是一样的！事实上，选了 72 这个新加的点，因为其权值等于 选的点的左边点的权值 + 选的点的右边点的权值 - 选的点的权值，就相当于是 放弃原先选的点，而选其左右的点，也就是我们通过这样的操作达到了 后悔 的目的，取到了最优解。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e7+7;
struct node
{
    int val,id;

    bool operator < (const node &x)const
    {
        return val<x.val;
    }
};
struct lise
{
    int val,l,r;
}p[N];
int n,m,ans;
priority_queue<node>q;
bool vis[N];

void del(int x)
{
    p[x].l=p[p[x].l].l;
    p[x].r=p[p[x].r].r;
    p[p[x].l].r=x;
    p[p[x].r].l=x;
}

int main()
{
    scanf("%d%d",&n,&m);
    if(n<m*2)
    {
        printf("Error!");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i].val);
        p[i].l=i-1;
        p[i].r=i+1;
        q.push((node){p[i].val,i});
    }
    p[1].l=n,p[n].r=1;
    for(int i=1;i<=m;i++)
    {
        while(vis[q.top().id])
            q.pop();
        node now=q.top();
        q.pop();

        ans+=now.val;
        vis[p[now.id].l]=true;
        vis[p[now.id].r]=true;
        p[now.id].val=p[p[now.id].l].val+p[p[now.id].r].val-p[now.id].val;
        q.push((node){p[now.id].val,now.id});
        del(now.id);
    }

    printf("%d",ans);
    return 0;
}

其他例题：

CF1271D Portals

P3045 [USACO12FEB]Cow Coupons G

三、总结

事实上，后悔贪心 就是在 普通贪心 的基础上，加入了 可撤销原先选择的操作，而这样的操作还是要视具体题目而定。大体其实还是贪心的框架。

参考文献

维基百科

刘汝佳 《算法竞赛入门经典》