HDU 4268 – Alice and Bob [贪心]

点击打开HDU题目链接

题意

两个人分别有N个矩形,每个举行都知道长和宽。对于每个矩形,如果长和宽分别大于等于另外一个矩形的长和宽,那么这个举行覆盖另外一个矩形。问你第一个人的N个举行最多能覆盖多少个第二个人的矩形。

分析

对于第一个人的每个矩形,找出长和宽分别大于第二个人的所有矩形,贪心从小到大找出即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int maxn = 100005;
P A[maxn], B[maxn];
multiset<int> s;

int main() {
    int n, T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d%d", &A[i].first, &A[i].second);
        for (int i = 0; i < n; ++i)
            scanf("%d%d", &B[i].first, &B[i].second);
        sort(A, A + n), sort(B, B + n);
        int cnt = 0; s.clear();
        for(int i = 0, j = 0; i < n; ++i) {
            for(; j < n && B[j].first <= A[i].first; ++j)
                s.insert(B[j].second);
            auto pos = s.upper_bound(A[i].second);
            if(pos == s.begin()) continue;
            ++cnt, s.erase(--pos);
        }
        printf("%d\n", cnt);
    }
    return 0;
}

欢迎留言