[multiset][pair][贪心]hdoj 4268：Alice and Bob

大致题意：
    alice和bob每个人各有n张卡片，每张卡片都有自己的长和宽。现在规定对于alice的一张卡片a，和bob的一张卡片b。如果a的长和宽都大于等于b，则a可以覆盖b。每张卡片都只能覆盖和被覆盖一次。求alice用手中的卡片最多能覆盖多少bob的卡片。

 

大致思路：

    贪心+各种数据结构。

    贪心的策略是，从小到大枚举alice的每张卡片，每次都在bob的卡片中，挑出边长小于当前卡片的所有卡片。然后再在这些卡片中选出宽最小的可以被当前卡片覆盖的卡片。

    multiset的lower_bound函数请参见  http://blog.csdn.net/niushuai666/article/details/6734650

 

#include<utility>
#include<cstdio>
#include<vector>
#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
const int nMax=100100;
pair<int,int>app[nMax];pair<int,int>bpp[nMax];
multiset<int> stt;
int main() {
    int t,n,i,j,a,b,c,ans;
    scanf("%d",&t);
    while(t--)
    {
        stt.clear();
        ans=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&app[i].first,&app[i].second);
        }
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&bpp[i].first,&bpp[i].second);
        }
        sort(app,app+n);
        sort(bpp,bpp+n);
        int bpos=0;
        for(i=0;i<n;i++)
        {
            while(bpos<n&&bpp[bpos].first<=app[i].first)
            {
                stt.insert(bpp[bpos].second);
                bpos++;
            }
            if(stt.size()>=1)
            {
                multiset<int>::iterator it = stt.lower_bound(app[i].second);
                if(it==stt.end())it--;        
                if(it!=stt.begin()&&*it>app[i].second)it--;
                if (*it <= app[i].second ) {
                    stt.erase(it);
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}