2 2 1 2 3 4 2 3 4 5 3 2 3 5 7 6 8 4 1 2 5 3 4
1 2
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int maxn=1e5+5;
struct T {
int h;
int w;
bool operator < (const T & a) const {
return h<a.h;
}
};
void read(T * a,int n) {
for(int i=0; i<n; i++)
scanf("%d%d",&a[i].h,&a[i].w);
}
T a[maxn];
T b[maxn];
int ans;
int n;
multiset<int> st;
multiset<int>::iterator p;
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
read(a,n);
read(b,n);
sort(a,a+n);
sort(b,b+n);
st.clear();
ans=0;
int j=0;
for(int i=0; i<n; i++) {
while(j<n&&b[j].h<=a[i].h)
st.insert(b[j++].w);
if(st.empty()) continue;
p=st.lower_bound(a[i].w);
if(p==st.end()||*p>a[i].w&&p!=st.begin()) p--;
if(*p<=a[i].w) {
ans++;
st.erase(p);
}
}
printf("%d\n",ans);
}
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
hdu 4268 Alice and Bob(贪心+multiset+二分)
原文:http://blog.csdn.net/acm_baihuzi/article/details/47470245