跃迁引擎启动

HDu6003 Problem Buyer 题解

发表于 更新于 分类于 阅读次数：

题意

给定 $n$ 条线段和 $m$ 个询问点，任意取出一些线段，使得所有询问点可以被不同的线段覆盖，即不能有两个点只被一条线段覆盖，求最少要取出多少线段满足这个条件。

其中 $2\le n,m \le 10^5$。

题解

赛中冲的算法是线段覆盖，对目标点询问未被覆盖次数，取 $\min$ 后加一。

显然非常的假，你不能保证剩余的线段一定能覆盖所有其他的点。

将线段端点和询问点，拆成事件做扫描线，对于相同端点的事件，先加入，再询问，最后删除。

对于询问，看能不能覆盖这个点，即有当前存在事件集合非空，答案是线段数减去集合大小，并要拿去一个线段，因为这个线段不能对其他询问产生贡献。这里需要贪心的想，右端点应该尽量靠前，这样才会减少对后面询问的影响。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#ifdef XLor
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
  #define dbg(...)
#endif
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

int n, m, a[maxn], b[maxn], c[maxn];

int main() {
    int T, kase = 0; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        multiset<int> st;
        vector<PII> ev;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", a + i, b + i);
            ev.push_back({a[i], -i});
            ev.push_back({b[i], i});
        }
        for (int i = 1; i <= m; i++) {
            scanf("%d", c + i);
            ev.push_back({c[i], 0});
        }
        sort(ev.begin(), ev.end());
        int ans = 0, f = 1;
        for (auto& x: ev) {
            if (x.second == 0) {
                // dbg(st.size());
                if (st.empty()) {
                    f = 0; break;
                }
                ans = max(ans, n - (int)st.size() + 1);
                st.erase(st.begin());
            } else if (x.second > 0) {
                int id = x.second;
                // dbg(id, a[id], b[id]);
                if (st.count(b[id])) st.erase(st.find(b[id]));
            } else {
                int id = -x.second;
                // dbg(a[id], x.first);
                st.insert(b[id]);
            }
        }
        printf("Case #%d: ", ++kase);
        if (!f) puts("IMPOSSIBLE!");
        else printf("%d\n", ans);
    }
    return 0;
}