这题呢.. 以前也做过其中的一小部分。只是综合起来就不会了!
我会变得强大的!
思路很巧妙!加油!以后要多做做这种题目!
#include<iostream> #include<algorithm> #define MN 111111 using namespace std; struct Node { int h,w,id; }node[MN<<1]; int tree[MN<<1],tot,N; int lowbit( int x ){ return x&-x; } bool cmpw( Node a,Node b ) { return a.w<b.w; } bool cmp( Node a,Node b ) { if( a.h!=b.h ) return a.h<b.h; if( a.w!=b.w ) return a.w<b.w; return a.id>b.id; } void lisan() { int temp=111111111;tot=0; for( int i=0;i<2*N;i++ ) { if( node[i].w!=temp ) { temp=node[i].w; node[i].w=++tot; } else node[i].w=tot; } } int find( int x ) { int ret=0; while( x ) { ret+=tree[x]; x-=lowbit(x); } return ret; } int bsearch( int x ) { int l=1,r=tot,m; while( (m=(l+r)/2),l<r ) { if( find(m)>=x ) r=m; else l=m+1; } return m; } void update( int x,int v ) { while( x<=tot ) { tree[x]+=v; x+=lowbit(x); } } int main() { int T; scanf( "%d",&T ); while( T-- ) { memset( tree,0,sizeof(tree) ); scanf( "%d",&N ); for( int i=0;i<N;i++ ) { scanf( "%d %d",&node[i].h,&node[i].w ); node[i].id=0; } for( int i=N;i<2*N;i++ ) { scanf( "%d %d",&node[i].h,&node[i].w ); node[i].id=1; } sort( node,node+2*N,cmpw ); lisan(); sort( node,node+2*N,cmp ); int ans=0,k; for( int i=0;i<2*N;i++ ) { if( node[i].id==1 ) update(node[i].w,+1); else { k=find(node[i].w); if( k==0 ) continue; int at=bsearch(k); update(at,-1); ans++; } } printf( "%d\n",ans ); } return 0; }