贪心:按照宽从小到大,高从小到大,将alice和bob的卡片排序,如果宽高相同,则alice的在后面。这样所有卡片排成一排了。
每次找到alice的卡片之后,覆盖她前面的最接近她的bob的那张卡片(尽量让这张卡片最有用),然后去除掉。
#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 //#pragma comment(linker, "/STACK:36777216") ///传说中的外挂 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; }