首页 > 代码库 > HDU 4268
HDU 4268
http://acm.hdu.edu.cn/showproblem.php?pid=4268
学会了multiset的用法,与set不同的是这个可以插入相同元素
对w排序,对合适的w用multiset插入对应的h,logn完成查找
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <cmath>#include <set>using namespace std ;struct node { int w,h ; }a[100005],b[100005] ;int cmp(node x,node y){ if(x.w==y.w)return x.h<y.h ; return x.w<y.w ;}int main(){ int t ; scanf("%d",&t) ; while(t--) { int n ; scanf("%d",&n) ; for(int i=0 ;i<n ;i++) scanf("%d%d",&a[i].w,&a[i].h) ; for(int i=0 ;i<n ;i++) scanf("%d%d",&b[i].w,&b[i].h) ; sort(a,a+n,cmp) ; sort(b,b+n,cmp) ; int ans=0 ; multiset <int> s ; int j=0 ; for(int i=0 ;i<n ;i++) { while(j<n && b[j].w<=a[i].w) { s.insert(b[j].h) ; j++ ; } if(!s.size())continue ; multiset <int> :: iterator it=s.upper_bound(a[i].h) ; if(it!=s.begin()) { it-- ; s.erase(it) ; ans++ ; } } printf("%d\n",ans) ; } return 0 ;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。