hdu4268贪心

题意:

思路:

      明显是贪心,但是有一点很疑惑,如果以别人为主,每次都用自己最小的切能覆盖敌人的方法就wa,而以自己为主,去覆盖自己可能覆盖的最大就ac了,证明不了,总感觉这东西在孙子兵法里会有,,解题过程就是先吧两个人的所有卡片放一起以 长 小的在前面,如果 长 相等 id 大的(被覆盖那个)在前面排序,保证每一个卡片能覆盖的一定在自己的前面,然后从1开始跑循环,如果当前的点是被覆盖的点,那么直接把他的y扔进set里,否则就从set里取出一个自己能覆盖的最大的那个卡片,这样遍历到最后就行了,我忘记了题目中的y可能不可能重复了,如果可以重复的话直接把set改成muitiset就行了…

#include<stdio.h>
#include<algorithm>
#include<map>
#include<set>#define N_max 220000
#define inf 2000000000

using namespace std;typedef struct
{
    int h ,w ,key;
}CARD;CARD card[N_max];bool camp(CARD x ,CARD y)
{
    return x.h < y.h || x.h == y.h && x.w < y.w
    || x.h == y.h && x.w == y.w && x.key < y.key;
}int main ()
{
    int t ,i ,n ,sum;
    scanf("%d" ,&t);
    while(t--)
    {
        scanf("%d" ,&n);
        for(i = 1 ;i <= n ;i ++)
        {
            scanf("%d %d" ,&card[i].h ,&card[i].w);
            card[i].key = 1;
        }
        for(i = 1 ;i <= n ;i ++)
        {
            scanf("%d %d" ,&card[i + n].h ,&card[i + n].w);
            card[i + n].key = 0;
        }
        map<int ,int >mark;
        set<int>st;
        sort(card + 1 ,card + n + n + 1 ,camp);
        sum = 0;
        st.insert(inf);
        for(n *= 2 ,i = 1 ;i <= n ;i ++)
        {
            if(card[i].key)
            {
                int now = *st.lower_bound(-card[i].w);
                if(now == inf) continue;
                sum ++;
                mark[now] --;
                if(!mark[now])
                st.erase(now);
            }
            else
            {
                st.insert(-card[i].w);
                mark[-card[i].w] ++;
            }
        }
        printf("%d\n" ,sum);
    }
    return 0;
}