首页 > 代码库 > hdu 4268 Alice and Bob(multiset)
hdu 4268 Alice and Bob(multiset)
# include<stdio.h> # include<algorithm> # include<iostream> # include<string.h> # include<map> # include<set> # include<vector> using namespace std; struct node { int h; int w; }; struct node a[100010],b[100010]; bool cmp(node a1,node a2) { if(a1.h==a2.h) return a1.w<a2.w; return a1.h<a2.h; } int main() { int t,i,n,p; multiset<int>num;///可以插入相同元素,set只能插入不同元素 multiset<int>::iterator it; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0; i<n; i++) scanf("%d%d",&a[i].h,&a[i].w); for(i=0; i<n; i++) scanf("%d%d",&b[i].h,&b[i].w); sort(a,a+n,cmp); sort(b,b+n,cmp); int p=0; int ans=0; num.clear(); for(i=0; i<n; i++) { while(p<n&&a[i].h>=b[p].h) { num.insert(b[p].w); p++; } if(num.empty()) continue; it=num.upper_bound(a[i].w);///返回大于等于a[i].w的第一个元素 //set if(it!=num.begin()) { ans++; it--;///小于a[i].w num.erase(it);///相同的元素都会删除 } } printf("%d\n",ans); } return 0; }
hdu 4268 Alice and Bob(multiset)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。