算法基础算法

偷k个房间的打家劫舍问题：双向链表维护的反悔贪心策略

字数统计: 2.3k字   |   阅读时长: 10分
,

摘要: 贪心过程自动反悔的精巧设计

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们继续看一个反悔贪心算法的精巧设计。本题首先比较容易想到一种贪心思路，但有些问题，需要反悔机制进行纠正。而反悔机制的设计是通过在贪心选择当前节点之后，不将该节点删除，而是对当前节点的权值进行一些修改，使得如果后续再选到当前节点，就自动相当于进行了反悔。

两点有两个，一个是通过修改节点的方式使得按原有贪心策略选择就自动进行了反悔，另一个是通过双向链表在节点的插入删除过程中维护相邻关系。

恰好偷k个房间的打家劫舍

圆周上有 n 个坑，均可以种树。

为了保证每棵树都有充足养料，不能在相邻的两个坑中种树。

另一方面，必须恰好种 k 棵树。如果无法把 k 棵树都种上，则返回 Error。

每个坑有一个盈利能力 $p[i]$，即若在第 $i$ 个坑种树，可以盈利 $p[i]$。

问最大获利是多少。

1
2
3
4
5
6
输入格式
输入的第一行包含两个正整数 n, m
第二行 n 个整数，第 i 个代表 Ai。

输出格式
输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出 Error!。

输入输出样例
输入
7 3
1 2 3 4 5 6 7
输出
15
输入
7 4
1 2 3 4 5 6 7
输出
Error!

算法：反悔贪心

如果没有种 k 棵树的限制，就是一个标准的打家劫舍问题，参考文章 打家劫舍：不相邻子序列最大和问题。

一种贪心策略是，直接在合法情况下选择最大价值，用堆维护所有位置，每次选择一个价值最大的点，然后标记其相邻左右两个点均不可再选，然后继续从堆中选取价值最大的点，以此类推。

但是这个策略是错的，原因在于选了最大价值的点，那么相邻两个点就不能选了，而选择相邻两个点得到的价值可能更大。于是就有了反悔贪心思路的雏形：先贪心地选择最大价值，如果发现选择相邻的两个点更好，就进行反悔。

下面的问题是如何设计反悔策略。

假设有 A, B, C, D 四个点，价值分别为 a, b, c, d。其中 $b$ 最大，按照贪心策略，我们会先选出 $b$，此时 $a$ 和 $c$ 就会被标记不能选，下一步我们还可以选到 $d$，于是得到答案 $b + d$。

但是这里 $a + c > b + d$，贪心策略得到的 $b + d$ 不对。也就是这里我们需要一种反悔机制，撤销对 $b$ 的选择，改为 $a + c$。

这里的精巧设计是：当选择 $b$ 时，将 $b$ 弹出后，再新增一个价值为 $a + c - b$ 的点 $P$ 进去，后续按照贪心策略如果选择了 $P$，就相当于撤销 $b$ 选择 $a + c$ 的一步反悔操作。

下面的问题是如何快速插入 P 点并维护 P 点的相邻点，当我们后续选出 P 点，即执行反悔时，需要标记 P 的相邻节点（即 a, c 两点除了 b 之外的另一个相邻点）不可选。在节点不断插入删除的过程中维护相邻关系是双向链表擅长处理的。

因此我们用双向链表维护所有点的相邻关系，链表节点的内容为点的 id：

1
list<int> l;

堆中的节点包含点的 id 及其对应的价值 p，及其对应的链表指针：

1
2
3
4
5
6
7
8
struct Point
{
    int id;
    int p;
    list<int>::iterator iter;
    Point(){}
    Point(int id, int p, list<int>::iterator iter):id(id),p(p),iter(iter){}
};

堆中排序的规则是按照点的利润从大到小：

1
2
3
4
5
6
7
8
9
struct HeapCmp
{
    bool operator()(const Point& i1, const Point& i2) const
    {
        return i1.p < i2.p;
    }
};

priority_queue<Point, vector<Point>, HeapCmp> pq;

于是算法的流程就是不断取堆顶 b = pq.top().p 作为当前的选择，在答案中增加 b，访问到该点对应在双向链表中的位置 it = pq.top().iter，找到其相邻两个节点 it.prev，it.next，价值分别为 a, c，将其标记为不可选，然后从双向链表中删掉。新增点 P，在链表中仍为 it 节点，id 不变，将其价值改为 a + c - b。

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <unordered_set>

using namespace std;

struct Point
{
    int id;
    int p;
    list<int>::iterator iter;
    Point(){}
    Point(int id, int p, list<int>::iterator iter):id(id),p(p),iter(iter){}
};

struct HeapCmp
{
    bool operator()(const Point& i1, const Point& i2) const
    {
        return i1.p < i2.p;
    }
};

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for(int i = 0; i < n; ++i)
        cin >> p[i];

    if(k > n / 2)
    {
        cout << "Error!" << endl;
        return 0;
    }

    list<int> l(n);
    int id = 0;
    for(auto it = l.begin(); it != l.end(); it++)
    {
        *it = id;
        id++;
    }
    priority_queue<Point, vector<Point>, HeapCmp> pq;

    for(auto it = l.begin(); it != l.end(); it++)
    {
        int id = *it;
        pq.push(Point(id, p[id], it));
    }

    unordered_set<int> setting; // 不可选的 id

    int ans = 0;
    while(k > 0 && !pq.empty())
    {
        if(setting.count(pq.top().id) > 0)
        {
            pq.pop();
            continue;
        }
        k--;
        // 贪心地选 b 点
        int b = pq.top().p;
        ans += b;
        auto it = pq.top().iter;
        pq.pop();

        // 访问到 a, c 两点
        auto next_it = next(it);
        if(next_it == l.end())
            next_it = l.begin();
        auto prev_it = it;
        if(prev_it == l.begin())
            prev_it = l.end();
        prev_it = prev(prev_it);

        if(prev_it == it || prev_it == next_it)
        {
            // 只剩1个或2个节点
            continue;
        }

        int a  = p[*prev_it];
        int c  = p[*next_it];

        // 标记 a, c 不可选
        setting.insert(*next_it);
        setting.insert(*prev_it);
        l.erase(prev_it);
        l.erase(next_it);

        // 新增 P 点，链表节点仍为 it，id 不变，值变为 a + c - b
        p[*it] = a + c - b;
        pq.push(Point(*it, a + c - b, it));
    }
    cout << ans << endl;
}

最多偷k个房间的打家劫舍

一条直线上有 n 个坑，均可以种树。

为了保证每棵树都有充足养料，不能在相邻的两个坑中种树。

另一方面，由于树种不够，最多种 k 棵树。

每个坑有一个盈利能力 $p[i]$，即若在第 $i$ 个坑种树，可以盈利 $p[i]$。

问最大获利是多少。

1
2
3
4
5
6
输入格式
第一行，两个正整数 n,k。
第二行，n 个整数，第 i 个数表示在直线上从左往右数第 i 个坑种树的获利。

输出格式
输出一个数，表示 cyrcyr 种树的最大获利。

输入输出样例
输入
6 3
100 1 -1 100 1 -1
输出
200

算法：反悔贪心

与上一题相比，变化有两点，一个是树坑呈直线而不是环形，这样两个端点位置的坑可以同时选。

另一个是最多选 k 个，而不是恰好选 k 个。

因此还是按照上一题的反悔贪心算法，只是在维护节点相邻关系时做一些修改，同时也保留选出的坑小于 k 个的情况的答案。

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <unordered_set>

using namespace std;
using ll = long long;

struct Point
{
    int id;
    int p;
    list<int>::iterator iter;
    Point(){}
    Point(int id, int p, list<int>::iterator iter):id(id),p(p),iter(iter){}
};

struct HeapCmp
{
    bool operator()(const Point& i1, const Point& i2) const
    {
        return i1.p < i2.p;
    }
};

int main()
{
    // fstream fin("P1484_6.in");
    int n, k;
    cin >> n >> k;
    // fin >> n >> k;
    vector<int> p(n);
    for(int i = 0; i < n; ++i)
        // fin >> p[i];
        cin >> p[i];

    list<int> l(n);
    int id = 0;
    for(auto it = l.begin(); it != l.end(); it++)
    {
        *it = id;
        id++;
    }
    priority_queue<Point, vector<Point>, HeapCmp> pq;

    for(auto it = l.begin(); it != l.end(); it++)
    {
        int id = *it;
        pq.push(Point(id, p[id], it));
    }

    unordered_set<int> setting; // 不可选的 id

    ll ans = 0;
    while(k > 0 && !pq.empty() && pq.top().p > 0)
    {
        if(setting.count(pq.top().id) > 0)
        {
            pq.pop();
            continue;
        }
        k--;
        // 贪心地选 b 点
        int b = pq.top().p;
        ans += b;
        auto it = pq.top().iter;
        pq.pop();

        // 访问到 a, c 两点
        auto next_it = next(it);
        auto prev_it = it;
        if(prev_it == l.begin())
            prev_it = l.end();
        else
            prev_it = prev(prev_it);

        if(prev_it == l.end() && next_it == l.end())
        {
            // 只剩 1 个节点
            continue;
        }

        if(prev_it != l.end() && next_it != l.end())
        {
            int a  = p[*prev_it];
            int c  = p[*next_it];

            // 新增 P 点，链表节点仍为 it，id 不变，值变为 a + c - b
            p[*it] = a + c - b;
            pq.push(Point(*it, a + c - b, it));
        }

        // 标记 a, c 不可选
        if(prev_it != l.end())
        {
            setting.insert(*prev_it);
            l.erase(prev_it);
        }
        if(next_it != l.end())
        {
            setting.insert(*next_it);
            l.erase(next_it);
        }
    }
    cout << ans << endl;
}
Share