hdu 4268 贪心+set lower

http://acm.hdu.edu.cn/showproblem.php?pid=4268

A想用手里的牌尽量多地覆盖掉B手中的牌..

牌有h和w

问A手中的牌最多能覆盖B多少张牌

iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

#include<set>

using namespace std;

 struct S

 {

    int a,b,c;

 }p[200010];

 int cmp(S M,S N)

 {

     if(M.a!=N.a) return M.a<N.a;

     if(M.b!=N.b) return M.b<N.b;

     return M.c>N.c;

 }

 int main()

 {

     int t,n;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         for(int i=0;i<n;i++)

            scanf("%d%d",&p[i].a,&p[i].b),

            p[i].c=0;

         for(int i=n;i<2*n;i++)

            scanf("%d%d",&p[i].a,&p[i].b),

            p[i].c=1;

         sort(p,p+2*n,cmp);

         int ans=0;

         set<int> s;

         for(int i=0;i<2*n;i++)

         {

             if(p[i].c)

                s.insert(p[i].b);

             else

             if(!s.empty()&&*s.begin()<=p[i].b)

             {

                 set <int>::iterator it=s.upper_bound(p[i].b);

                 it--;

                 ans++;

                 s.erase(it);

             }

         }

         printf("%d\n",ans);

     }

 }

巴特西

hdu 4268 贪心+set lower_bound用法

最新文章

热门文章