大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
Alice and Bob
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2901 Accepted Submission(s): 941
Please pay attention that each card can be used only once and the cards cannot be rotated.
For each case, the first line is a number N which means the number of cards that Alice and Bob have respectively. Each of the following N (N <= 100,000) lines contains two integers h (h <= 1,000,000,000) and w (w <= 1,000,000,000) which means the height and width of Alice’s card, then the following N lines means that of Bob’s.
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
题意：
(n<=1e5)如今A想用自己的矩形覆盖B的矩形。一个矩形覆盖还有一个矩形的条件是宽和高都不还有一个矩形相应的宽和高小。如今问A最多能覆盖B的多少个矩形。每一个矩形最多覆盖一个还有一个矩形。且矩形不能旋转。
然后对于A的每个矩形。找一个w<=自己w.h<自己H且尽量接近的B的矩形覆盖即可了。
覆盖后删除这两个矩形。对于找上述条件的矩形能够用multiset维护。
可是比赛时换了种姿势用线段树写了发。
思路都差点儿相同。离散化。维护区间和。找小于等于p且最靠右的位置。
#include <iostream> #include<stdio.h> #include<algorithm> using namespace std; #define lson L,mid,ls #define rson mid+1,R,rs const int maxn=100010; int num[maxn<<3];//离散化后有2*n忘了改大空间了。坑struct node{ int w,h;} ag[maxn],bg[maxn];int H[maxn<<1];inline bool cmp(const node &a,const node &b){ if(a.w==b.w) return a.h<b.h; return a.w<b.w;}void build(int L,int R,int rt){ num[rt]=0; if(L==R) return ; int ls=rt<<1,rs=ls|1,mid=(L+R)>>1; build(lson); build(rson);}void update(int L,int R,int rt,int p,int d){ if(L==R) { num[rt]+=d; return; } int ls=rt<<1,rs=ls|1,mid=(L+R)>>1; if(p<=mid) update(lson,p,d); else update(rson,p,d); num[rt]=num[ls]+num[rs];}int qu(int L,int R,int rt,int p){ if(!num[rt]) return -1; if(L==R) return L; int ls=rt<<1,rs=ls|1,mid=(L+R)>>1,pos=-1; if(p<=mid) return qu(lson,p); if(num[rs]) pos=qu(rson,p); if(pos!=-1) return pos; return qu(lson,p);}int main(){ int t,n,i,m,p,ans; scanf("%d",&t); while(t--) { m=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&ag[i].h,&ag[i].w); H[m++]=ag[i].h; } for(i=0;i<n;i++) { scanf("%d%d",&bg[i].h,&bg[i].w); H[m++]=bg[i].h; } sort(ag,ag+n,cmp); sort(bg,bg+n,cmp); sort(H,H+m); m=unique(H,H+m)-H; build(1,m,1); ans=p=0; for(i=0;i<n;i++) { while(p<n&&bg[p].w<=ag[i].w) update(1,m,1,lower_bound(H,H+m,bg[p].h)-H+1,1),p++; int pos=qu(1,m,1,lower_bound(H,H+m,ag[i].h)-H+1); if(pos!=-1) { ans++; update(1,m,1,pos,-1); } } printf("%d\n",ans); } return 0;}
版权声明：本文博主原创文章，博客，未经同意不得转载。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116762.html原文链接：https://javaforall.net
