## HDU 4268 Alice and Bob(贪心+数据结构)

2019年02月10日 ⁄ 综合 ⁄ 共 1223字 ⁄ 字号 评论关闭

```#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 100005
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
using namespace std;

struct node {
int x,y;
int kind;
} card[MAX * 2];
typedef multiset<int> SET;
typedef multiset<int> ::iterator IT;

bool cmp(node a,node b) {
if(a.x != b.x) return a.x < b.x;
if(a.y != b.y) return a.y < b.y;
return a.kind > b.kind;
}

int n;

int main() {
int T,i;
cin >> T;
while(T --) {
SET my;
scanf("%d",&n);
for(i=0; i<n*2; i++) {
scanf("%d%d",&card[i].x,&card[i].y);
if(i >=0 && i < n) card[i].kind = 0;
else card[i].kind = 1;
}
sort(card,card+n*2,cmp);
int ans = 0;
for(i=0; i<n*2; i++) {
if(card[i].kind == 1) my.insert(card[i].y);
else if(card[i].kind == 0 && ! my.empty() && *my.begin() <= card[i].y) {

IT it = my.upper_bound(card[i].y);
it --;
//cout << *it << ' ' << card[i].y << endl;
ans ++;
my.erase(it);
}
}
printf("%d\n",ans);
}
return 0;
}
```