0x00-基础算法-(6)-贪心 - Be Grinder,for Better

贪心

贪心算法（greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是任何时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性（通常用反证法或数学归纳法证明）。

贪心类问题无疑是基础算法中难度最大的，难点在于思维的跳跃性，没有固定的解题模式，往往是一类题一种解法或结论。

总而言之：贪心是指每次找局部最优解，就可以找到全局最优解，所以贪心一般要求函数是单峰的。动态规划的限制会少一些，一般是枚举了空间中的所有值，找出了最优解。这两个算法一般是从经验出发来判断，所以要多做题。

下面介绍一些常见的贪心问题以及其对应的启发式策略。

区间问题

区间问题最重要的其实不是选择按左端点还是右端点排序【因为按左端点排序和按右端点排序的解法可以相互转换】，而是排序后，应该优先考虑包含区间还是被包含区间，这才是本质问题。

最少覆盖区间点数和最大不相交区间数，要优先考虑被包含区间
区间合并、区间分组、区间覆盖，要优先考虑包含区间

最少覆盖区间点数

数轴上有若干区间，在数轴上选点，使得每个区间内至少包含一个点，求选择的点的最小数量。

贪心策略：
Step1: 区间按左端点从小到大排序
Step2: 按倒序依次枚举每个区间：
如果当前区间已经包含该点，则直接continue；
否则，选择当前区间左端点

AcWing-905.区间选点

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int n;
vector<PII> segs;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        segs.push_back({l, r});
    }
    
    // step1: 按左端点排序
    sort(segs.begin(), segs.end());
    
    int res = 0;
    int st = INF;
    // step2: 倒序枚举
    for (int i = n - 1; i >= 0; i --) {
        // 无交集
        if (segs[i].second < st) {
            res ++;
            st = segs[i].first;
        }
    }
    
    cout << res << endl;
    
    return 0;
}

最大不相交区间数

数轴上有若干区间，选择其中尽可能多的区间，使得选中的区间之间互不相交。

贪心策略：
Step1: 区间按左端点从小到大排序
Step2: 按倒序依次枚举每个区间：
如果两个区间相交，则直接continue；
否则，选择当前区间(res ++)，并把比较区间更新为当前区间

AcWing-908.最大不相交区间数量

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int n;
vector<PII> segs;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++)  {
        int l, r;
        scanf("%d %d", &l, &r);
        segs.push_back({l, r});
    }

    // step1: 按左端点排序
    sort(segs.begin(), segs.end());
    
    int res = 0;
    int st = INF;
    // step2: 倒序枚举
    for (int i = n - 1; i >= 0; i --) {
        // 无交集
        if (segs[i].second < st) {
            res ++;
            st = segs[i].first;
        }
    }

    cout << res << endl;

    return 0;
}

综上，可得结论：最少覆盖区间点数 == 最大不相交区间数
因为如果几个区间能被同一个点覆盖，说明它们相交了，所以有几个点就是有几个不相交区间

区间合并

数轴上有若干区间，要求合并所有有交集的区间，求合并后的区间个数。

贪心策略：
Step1: 区间按左端点从小到大排序
Step2: 按顺序依次枚举区间：
如果当前区间与上一个区间没有交集，则把上一个区间放入合并数组内，当前区间更新为上一个区间;
否则，把当前区间与上一个区间合并，更新上一个区间的右端点的最大值

AcWing-803.区间合并

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int n;
vector<PII> segs;

void merge(vector<PII> &segs) {
    vector<PII> res;
    
    // step1: 按左端点对区间排序
    sort(segs.begin(), segs.end());
    
    // step2: 按顺序依次枚举区间
    int st = -INF, ed = -INF;
    for (int i = 0; i < segs.size(); i ++) {
        // 无交集
        if (ed < segs[i].first) {
            if(st != -INF) res.push_back({st, ed});
            st = segs[i].first, ed = segs[i].second;
        }
        // 有交集
        else ed = max(ed, segs[i].second);
    }
    if(st != -INF) res.push_back({st, ed});

    segs = res;
}

int main() {
    cin >> n;
    
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        segs.push_back({l, r});
    }
    
    merge(segs);
    
    cout << segs.size() << endl;
    
    return 0;
}

区间分组

数轴上有若干区间，给这些区间分组，使得每组内的区间互不相交，求最小分组数量。

贪心策略：
Step1: 区间按左端点从小到大排序
Step2: 用一个小根堆维护当前分组(pair<右端点, 分组id>)，按顺序依次枚举每个区间:
每次取出堆顶的组，如果组内区间与当前区间无交集，则让当前区间加入该组，并更新区间右端点;
否则，以当前区间右端点新建一个分组，加入到小根堆中

AcWing-906.区间分组

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

vector<PII> seg;

int n;

int main() {
    cin >> n;
    seg.resize(n);
    for (int i = 0; i < n; i ++) {
        scanf("%d %d", &seg[i].first, &seg[i].second);
    }
    sort(seg.begin(), seg.end());

    priority_queue<PII, vector<PII>, greater<PII>> pq;
    for (int i = 0; i < n; i ++) {
        // 组数不为空，并且组内区间与当前区间无交集
        if (!pq.empty() && pq.top().first < seg[i].first) {
            auto t = pq.top(); pq.pop();
            t.first = seg[i].second;
            pq.push(t);
        }
        // 有交集
        else {
            pq.push({seg[i].second, pq.size() + 1});
        }
    }

    cout << pq.size() << endl;

    return 0;
}

区间分组也是最大区间厚度(最多区间重叠部分)，这里有一种 $O(n)$ 的解法:

思路：我们可以把所有开始时间和结束时间排序，遇到开始时间就把需要的教室加1，遇到结束时间就把需要的教室减1,在一系列需要的教室个数变化的过程中，峰值就是多同时进行的活动数，也是我们至少需要的教室数。

参考题解：https://www.acwing.com/solution/content/8902/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100100;

int n;
int b[2 * N], idx;

int main() {
    scanf ("%d", &n);
    for(int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;//标记左端点为偶数。
        b[idx ++] = r * 2 + 1;// 标记右端点为奇数。
    }

    sort(b, b + idx);

    int res = 1, t = 0;
    for(int i = 0; i < idx; i ++) {
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}

区间覆盖

数轴上有若干区间，选择其中尽可能少的区间，覆盖一个题给指定线段。

贪心策略：
Step1: 区间按左端点从小到大排序, 初始赋值 st = tar.first, ed = tar.second
Step2: 按顺序依次枚举区间:
首先在这些segs中挑出满足左端点 <= st的线段，
然后在这些线段中，选择second最大的那个作为覆盖区间，并把st更新为该区间的second
重复Step2，直到r >= ed
首先在这些segs中挑出满足左端点 <= st的线段，
注意，会有无解情况，因此需要设置flag来判断:
① 找不到满足first <= st的线段，或者这些区间全与 $[st,ed]$ 不相交(r < st)
② 遍历完整个区间后r仍然 < ed

AcWing-907.区间覆盖

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int n;
PII tar;
vector<PII> segs;

int main() {
    cin >> tar.first >> tar.second;
    cin >> n;
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        segs.push_back({l, r});
    }

    sort(segs.begin(), segs.end());

    int res = 0;
    bool flag = false;
    int st = tar.first, ed = tar.second;
    for (int i = 0; i < n; i ++) {
        int j = i, r = -INF;
        while  (j < n && segs[j].first <= st) {
            r = max(r, segs[j].second);
            j ++;
        }

        if (r < st) {
            res = -1;
            break;
        }

        res ++;
        if (r >= ed)  {
            flag = true;
            break;
        }

        st  = r;
        i = j - 1;
    }

    if (!flag) res = -1;
    cout << res << endl;

    return 0;
}

其它经典贪心

合并果子

有n堆果子，需要两两合并，经过n-1次合并成 1堆果子，求合并最少需要花费的体力。[把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和]

贪心策略
每次选择最小重量的两堆进行合并，即为最小花费体力。
ps:整个合并过程就是一个二叉树，每个结点的贡献次数就是结点到根结点的距离。

AcWing-148.合并果子

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int n;

int main() {
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i ++) {
        int x;
        scanf("%d", &x);
        pq.push(x);
    }
    
    long long res = 0;
    while(pq.size() != 1) {
        int t1 = pq.top(); pq.pop();
        int t2 = pq.top(); pq.pop();
        
        int t = t1 + t2;
        res += t;
        pq.push(t);
    }
    
    cout << res << endl;
    return 0;
}

排队打水

有 $n$ 个人排队到 $1$ 个水龙头处打水，第 $i$ 个人装满水桶所需的时间是 $t_i$ ，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

贪心策略
由i的任意性，打水的时间总和为 ${t_{i_1}*(n-1) + t_{i_2}*(n-2) + ...t_{i_n}*(n-n)}$ ，也就是前缀和之和
要想让前缀和之和最小，显然从小到大排序即可

AcWing-913.排队打水

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 7;

int n;
int arr[N];
LL sum[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    
    sort(arr + 1, arr + n + 1);
    
    sum[0] = 0;
    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    
    LL res = 0;
    // 最后一个人的时间不用等
    for (int i = 1; i < n; i ++) {
        res += sum[i];
    }
    
    cout << res << endl;
    
    return 0;
}

货仓选址

贪心策略
显然，如果要使得 $\sum_{i=1}^n\left|A_i-A_k\right|$ 最小， ${\left|A_i-A_k\right|}$ 的几何意义是数轴上两点之间的距离。
那么可以分情况讨论：
当n是奇数，显然 $A_k$ 取排序后的中位数 $A_{\frac{n + 1}{2}}$ 是最优解
当n是偶数，显然 $A_k$ 取排序后的区间 $[A_{\frac{n + 1}{2}},A_{\frac{n + 1}{2}}]$ 内任意一点都是最优解，不妨取中位数

AcWing-104.货仓选址

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;
vector<int> a;

int main() {
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &a[i]);
    }
    
    sort(a.begin(), a.end());
    
    LL res = 0;
    for (int i = 0; i < n; i ++) {
        res += abs(a[i] - a[n / 2]);
    }
    
    cout << res << endl;
    
    return 0;
}

练习eg:

Acwing-122.糖果传递

耍杂技的牛/国王游戏

贪心策略
按照 ${w_{i} + s_{i}}$ 从小到大的顺序，来从高往低叠罗汉

Acwing-125.耍杂技的牛

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int n;
vector<PII> cows;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        int w, s;
        scanf("%d %d", &w, &s);
        cows.push_back({w, s});
    }
    
    sort(cows.begin(),cows.end(), [&](const PII&a,  const PII& b) -> bool{
       return a.first + a.second < b.first + b.second;
    });
    
    int res = -INF, sum = 0;
    for (int i = 0; i < n; i ++) {
        res = max(res, sum - cows[i].second);
        sum += cows[i].first;
    }
    
    cout << res << endl;
    
    return 0;
}

练习eg:

Acwing-114.国王游戏

Else

一个序列中任意两个值绝对值之差的最小值，就是把该序列排序后，相邻元素之差的最小值

数据结构与算法

Algorithm Template C++

本博客所有文章均采用 CC BY-NC-SA 4.0 协议，禁止商用，转载请注明出处！

0x10基础数据结构-(1)-链表上一篇

0x00-基础算法-(5)-前缀和&差分下一篇