hdu - 4268 - Alice and Bob


		题意：Alice和Bob都有N个矩形，问Alice的矩形最多能覆盖Bob的矩形多少个。每个矩形只能用一次，宽与高不能旋转。
 
——>>贪心，刚开始想到的策略是：将矩形按宽与高从大到小排序，然后Alice用最宽的去盖Bob的力所能及的最宽的，结果WA啦，现在发现，方向反了！贪心的策略应是从小到大，让Alice的每个矩形都能发挥其最大价值，即：取其中一维：宽度，从小到大来访问，每访问一个，在高度中从小到大搜出所有满足的高度，盖掉力所能及的最大的那个（multiset中有查找函数upper_bound(x)，返回第一个大于x的迭代器）。第一次用pair与multiset，滋味不错～～
[cpp]  
#include <cstdio>  
#include <vector>  
#include <set>  
#include <algorithm>  
  
using namespace std;  
  
typedef pair<int, int> pii;  
const int maxn = 100000 + 10;  
  
int main()  
{  
    int T, N, i, j, h, w;  
    scanf("%d", &T);  
    while(T--)  
    {  
        scanf("%d", &N);  
        vector<pii> A, B;  
        for(i = 0; i < N; i++)  
        {  
            scanf("%d%d", &h, &w);  
            A.push_back(make_pair(h, w));  
        }  
        for(i = 0; i < N; i++)  
        {  
            scanf("%d%d", &h, &w);  
            B.push_back(make_pair(h, w));  
        }  
        sort(A.begin(), A.end());  
        sort(B.begin(), B.end());  
        int cnt = 0;  
        multiset<int> s;  
        s.clear();  
        for(i = 0, j = 0; i < N; i++)  
        {  
            while(j < N && A[i].first >= B[j].first) s.insert(B[j++].second);  
            if(!s.empty())  www.zzzyk.com
            {  
                multiset<int>::iterator p = s.upper_bound(A[i].second);  
                if(p != s.begin())  
                {  
                    s.erase(--p);  
                    cnt++;  
                }  
            }  
        }  
        printf("%d\n", cnt);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,