[JZOJ5866]【NOIP2018模擬9.13】指引

Description

Input

Output

Sample Input

6
3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output

2

Data Constraint

Hint

?

---

?

?

貪心，把旅行者和出口的x坐標降序排序。

然后從前往后掃，如果是出口，就把y坐標插進set里，如果是旅行者，就查詢set里是否有大于等于他縱坐標的值，有的話就答案加一，把這個值從set里刪掉。

注意用multiset，并且不能刪除一個空的迭代器。

?

---

?

?

?

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
#define reg register
inline char gc() {static const int BS = 1 << 22;static unsigned char buf[BS], *st, *ed;if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);return st == ed ? EOF : *st++;
}
#define gc getchar
inline int read() {int res = 0;char ch=gc();bool fu=0;while(!isdigit(ch))fu|=(ch=='-'),ch=gc();while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=gc();return fu?-res:res;
}int TT, n;
struct date {int x, y, typ;bool operator < (const date &a) const {if (x == a.x) return y < a.y;return x > a.x;}
}da[200005];
int cnt;
int ans;
multiset <int> s;int main()
{
//    freopen("guide.in", "r", stdin);
//    freopen("guide.out", "w", stdout);TT = read(), n = read();for (reg int i = 1 ; i <= n ; i ++){int x = read(), y = read();da[++cnt] = (date){x, y, 1};}for (reg int i = 1 ; i <= n ; i ++){int x = read(), y = read();da[++cnt] = (date){x, y, 2};}sort(da + 1, da + 1 + cnt);for (reg int i = 1 ; i <= cnt ; i ++){if (da[i].typ == 2) s.insert(da[i].y);else if (!s.empty()) {set <int> :: iterator it = s.lower_bound(da[i].y);if (*it >= da[i].y) s.erase(*it), ans++;}}cout << ans << endl;return 0;
}

?