欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 16:19:54
...

大致题意:
    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;
}