首页 > 代码库 > 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 ;}
View Code