0%

CodeForce 555 B：Case of Fugitive 贪心

发表于 分类于 Valine：

架桥连接相邻岛

题目链接

https://codeforces.com/problemset/problem/555/B

题意

一维数轴上有若干个岛，岛屿岛之间不重叠，每个岛在数轴上有起点和终点。相邻两个岛上可以架桥，桥的两头要正好在岛上（不能多出去，但也要能架住）。现在给你一系列的桥，问能否把这些相邻的岛全部连起来。

数据范围：岛和桥的数量都\(\le2\times10^5\)

解题的（悲惨）心路历程

首先就想到了，应该把每个gap的min和max记录下来，然后开始猜想如何贪心 (因为是在王道上的贪心章节看到的题) 。然后就想到了把gap按min从大到小排序，按次序处理gap，每次找能满足当前(min最大)的gap的 可用的最长的bridge。。然后在脑海里成功证明了贪心选择性（开局能完成这个工作老兴奋了，后来blb尝试叉掉失败，我的分析是正确的，不愧是我）：

反证法：如果当前可用的最长的bridge不用在这个min最大的gap上（即假设该局部解不是全局解），那么有两种可能（假设这种情况下，min最大的gap记做\(G_0\)，此时放在\(G_0\)上的bridge是$ B'\(， 当前可用的最长的bridge为\)B_{max}\(。显然\)B'B_{max}$）：

  1. 这个bridge在全局解中完全没有出现。那么，把$ B'\(换成\)B_{max}\(是可行的（因为根据假设，\)B_{max}\(放在\)G_0$上是可行的）
  2. 这个bridge在全局解中出现了，但是放在了另一个gap上（设为\(G'\)）。根据前述gap的排序，\(G'.min\le G_0.min\)，既然\(B'\)能放在\(G_0\)上，说明\(G'.min\le G_0.min\le B'\)。同理，既然\(B_{max}\)能放在\(G'\)上，说明\(B'\le B_{max}\le G'.max\)。综合起来就是\(G'.min\le B' \le G'.max\)，因此\(B'\)可以放到\(G'\)上。又根据假设，\(B_{max}\)放在\(G_0\)上是可行的，所以\(B'\)和\(B_{max}\)可以交换位置，这样的解也是符合要求的。

根据上述分析，每次找能满足当前(min最大)的gap的 可用的最长的bridge，是某个可行解的一部分，按照这个贪心下去，一定能找到可行解。

主要工作已经完成了，屁颠屁颠写了个代码，大致是把gaps排序，bridges也排序，然后遍历每个gap，从前到后找可行bridge，找到就将其匹配，再另一个used数组上标记一下，表示这个bridge已经被用。算了一下复杂度是\(O(mn)\)，侥幸交了几发，然后就T了。

于是痛定思痛，开始优化复杂度。想到bridges是有序的，想到二分。写了个二分，找小于当前gap.max的最大bridge。找到之后再往后移，直到有没用到的(used[l] = false)，如果这个bridge\(\ge\)gap.min，就当做找到了；否则如果没找到或者bridge<gap.min就无解。这样写来是降了一点复杂度，多过了几个test，但是还是T了。原因应该是找used[l] = false花了不少时间。

大大小小调了很多东西，未果，扔给blb。得知C++中的set是平衡树，可用set来存bridges，利用其lower_bound方法实现上述的二分过程，同时返回的迭代器可直接用于erase方法。

遂尝试，结果WA了，仔细分析盲目分析数学分析xjb分析未果，遂扔给blb，出去遛弯。。。

后来blb发现了我的锅，在重载Bridge结构体的<的时候，只写了个长度的比较，没有把index加进去。由于set中元素的唯一性，导致了相同的Bridge就被替换掉了，遂顿悟。(此锅在后文中有详细总结)

题解

上面的贪心选择性已经证明了，这里直接给贪心思路：

把gaps以min为第一关键字，max为第二关键字，降序排序。依次处理每个gap，这样就相当于每次都在处理min最大的gap，记为\(G\)。现在需要找能放在\(G\)上的最大的bridge，只需找小于等于\(G.max\)最大的bridge就可，若找到的bridge的长度是\(\ge G.min\)的，就完成了这个gap的匹配，erase掉这个bridge即可；否则代表无解。

于是，把bridges放在set里，在找小于等于\(G.max\)最大的bridge时，就可以用到lower_bound方法。返回的迭代器可直接用于erase方法。

相似的问题

数轴上有n条线段，m个点，每个点最多可以分配给一个通过该点的线段，问是否每条线段都能被分配到一个符合要求的点，如何分配。

线段的起点终点就相当于本题的Gap的min和max，点的坐标就是各个bridge的长度。

需要记住的坑

  1. C++中set是平衡树实现，能执行lower_bound(key)操作，意思是在set中找大于等于key的最小的元素，复杂度是\(log\)的。通过重载$ <$运算符能或自定义比较函数够实现相反的（找小于等于key的最小的元素）。

  2. upper_bound是在set中找大于key的最小的元素

  3. set不允许有两个同样的key值，所以在重载运算符的时候要注意。一定要保证 想加入进set的两个对象的值不能相等。

    错误：

    1
    2
    3
    4
    5
    6
    7
    8
    struct Bridge {
        ll l;
        int index;

        bool operator<(const Bridge& b) const {
            return l > b.l;
        }
    };

    正确：

    1
    2
    3
    4
    5
    6
    7
    8
    struct Bridge {
        ll l;
        int index;

        bool operator<(const Bridge& b) const {
            return l > b.l || (l == b.l && index < b.index);
        }
    };

  4. 重载上述<运算符的时候(包括在优先队列里也是)，要给函数加const，否则会报错

    (至于为什么，现在也不是很懂，以后再研究。。。。)

  5. long long输出的格式符是%lld而不是%ld

AC代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Gap {
    ll min;
    ll max;
    int index;

    bool operator<(const Gap& g) const {
        if (min != g.min) {
            return min > g.min;
        }
        else {
            return max > g.max;
        }
    }
};

struct Bridge {
    ll l;
    int index;

    bool operator<(const Bridge& b) const {
        return l > b.l || (l == b.l && index < b.index);
    }
};

Gap g[200005];
int rec[200005];
set<Bridge> s;

int main() {

    int n, m;
    scanf("%d %d", &n, &m);

    ll p_l, p_r, l, r;
    scanf("%lld %lld", &p_l, &p_r);

    for (int i = 1; i < n; i++) {
        scanf("%lld %lld", &l, &r);
        g[i - 1] = (Gap){l - p_r, r - p_l, i - 1};
        p_l = l;
        p_r = r;
    }

    for (int i = 0; i < m; i++) {
        ll x;
        scanf("%lld", &x);
        s.insert((Bridge) {x, i + 1});
    }

    if (m < n - 1) {
        printf("No\n");
    }
    else {
        sort(g, g + n - 1);
        bool res = true;
        for (int i = 0; i < n - 1; i++) {
            auto it = s.lower_bound((Bridge){g[i].max, 0});
            if (it == s.end() || (*it).l < g[i].min) {
                res = false;
                break;
            }
            else {
                rec[g[i].index] = (*it).index;
                s.erase(it);
            }

        }

        if (res) {
            printf("Yes\n");
            for (int i = 0; i < n - 1; i++) {
                printf("%d ", rec[i]);
            }
            printf("\n");
        }
        else {
            printf("No\n");
        }
    }

    return 0;
}