贪心算法

这周的作业题是三道贪心题。说实话，事先没见过，要独立想出来还是很难的。毕竟贪心就是这样，就好像你明知道前面有一扇门，却在上面摸索半天，也找不到门把手在哪里。贪心也很想脑筋急转弯，假如没有灵机一动，想不到那个方法，就得一直坐牢下去。所以很多算法竞赛也喜欢考贪心，来考察变通能力。

很难说要怎样训练贪心题，或许寻求的就是一种感觉吧(就像语文一样)。找规律也很重要，再有就是数学推理能力。

拿这次的三道作业题举个例子，都是很经典的贪心题。

题目一——活动选择

原题链接——435. 无重叠区间 - 力扣（LeetCode）

image-20221023154608751

这道题，如果采用暴力求解，最坏时间复杂度甚至可以达到O(2^n)，在n很大时，是很吓人的。而贪心算法可以将复杂度降到O(nlogn)+O(n)，其中O(nlogn)是排序的时间复杂度。

我们的贪心策略是：在每次添加活动时，总是保证结束时间尽量早，这可以保证后续能尽可能多地添加活动。而何时开始，对后续添加是无影响的，只影响自己能不能向里面添加。依据这种策略，我们将每个活动按照结束时间排序，并依次检验开始时间是否大于目前的结束时间，如果满足，就添加进去(这个就是满足条件的结束时间最早的活动)，并更新结束时间。最后添加的活动数目就是答案。

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, ans = 1;
    vector<pair<int, int>> memo;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int start, end;
        cin >> start >> end;
        memo.push_back({start, end});
    }
    sort(memo.begin(), memo.end(), [](auto &p1, auto &p2) { return p1.second < p2.second; }); //按结束时间排序
    int right = memo[0].second;//维护结束时间right
    for (int i = 1; i < n; ++i)
        if (memo[i].first > right)//可以添加，即添加并更新
        {
            ++ans;
            right = memo[i].second;
        }
    cout << ans << endl;
    return 0;
}

题目二——小船过河

原题链接——1700 — Crossing River (poj.org)

image-20221023155536443

一种很直白的贪心思路就是：最快的来回跑，每次带一个过去，再把船划回来。然而，这种思路直接被样例否定掉了。按这种思路，总时间应当是10+1+5+1+2=19，事实上，快的和慢的一起走，把快的优势给抵消了。我们能不能让慢的一起走呢，如果还得它们划回来，那显然不会更好，然而，我们可以让在岸上的人划回来。样例的方案就是这样的：1,2过去，1回来；5,10过去，2回来；1,2过去。总时间2+1+10+2+2=17。来回跑的只能是最快的和次快的，否则一定更慢，所以总共就这两种方案，我们每次都选更优的一种。这样，每次可以送两个人过去，直到剩的人数<4，再分别讨论即可。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, tmp, ans = 0;
    vector<int> vec;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> tmp;
        vec.push_back(tmp);
    }
    sort(vec.begin(), vec.end());
    while (n >= 4)
    {
        ans += min(vec[n - 1] + vec[0] + vec[n - 2] + vec[0], vec[1] + vec[0] + vec[n - 1] + vec[1]);
        n -= 2;
    }
    if (n == 3)
        ans += vec[0] + vec[1] + vec[2];
    else if (n == 2)
        ans += vec[1];
    else
        ans += vec[0];
    cout << ans << endl;
    return 0;
}

题目三——补丁数组

原题链接——330. 按要求补齐数组 - 力扣（LeetCode）

image-20221023165051717

本题的贪心有些归纳法的性质。考虑这样一个问题，我们现在已经可以表示1~k的所有数，下一步应当添加谁呢？显然是k+1，因为它不能被表示，而添加后，就可以表示1~2k+1的所有数了(原来的当然可以表示，而k+1~2k+1只要将原来的都加上k+1就行了)。依据这样的方法，我们可以解决这道题了。我们用一个canGet代表现在已经能表示的1~k个数，并将包括的数继续加给canGet，之后如果原数组中没有canGet+1，就要添加它。直到能表示的范围包括了n。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long n, m, tmp, canGet = 0, ans = 0, i = 0;
    vector<int> vec;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> tmp;
        vec.push_back(tmp);
    }
    while (canGet < n)
    {
        if (i < vec.size() && canGet >= vec[i] - 1) //添加已经包括的数(或者本应下一个添加的数)
            canGet += vec[i++];
        else
        {
            canGet += canGet + 1;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}