Day3-H-Alice and Bob HDU4268

Alice and Bob's game never ends. Today, they introduce a new game. In this game, both of them have N different rectangular cards respectively. Alice wants to use his cards to cover Bob's. The card A can cover the card B if the height of A is not smaller than B and the width of A is not smaller than B. As the best programmer, you are asked to compute the maximal number of Bob's cards that Alice can cover.
Please pay attention that each card can be used only once and the cards cannot be rotated.

InputThe first line of the input is a number T (T <= 40) which means the number of test cases.
For each case, the first line is a number N which means the number of cards that Alice and Bob have respectively. Each of the following N (N <= 100,000) lines contains two integers h (h <= 1,000,000,000) and w (w <= 1,000,000,000) which means the height and width of Alice's card, then the following N lines means that of Bob's.
OutputFor each test case, output an answer using one line which contains just one number.
Sample Input

Sample Output

1

2

思路：依旧是贪心，但这个是二维问题，我们可以类比二位偏序问题来处理，先对h排序，扫描一遍Alice的数组，将每个小于等于h的Bob的元素入队，然后将小于等于w的元素出队
记录个数，此时无需关心h，因为入队的元素一定不大于现在的h，这里我们就要用到multiset这个容器来"当作队列"，因为其支持upper_bound/lower_bound的二分查找操作，
具体细节用代码感受一下：

struct Node {

    int h, w;

    Node(int _h = , int _w = ) : h(_h), w(_w){}

    bool operator<(const Node &a)const {

        return h < a.h || (h == a.h && w < a.w);

    }

};

vector<Node> v[];

multiset<int> q;

int main() {

    int T, n, sum;

    scanf("%d", &T);

    while(T--) {

        q.clear();

        sum = ;

        scanf("%d", &n);

        for (int i = ; i < ; ++i) {

            v[i].clear();

            for (int j = ; j < n; ++j) {

                int t1, t2;

                scanf("%d%d", &t1, &t2);

                v[i].push_back(Node(t1, t2));

            }

        }

        sort(v[].begin(), v[].end()), sort(v[].begin(), v[].end());

        for (int i = , j = ; i < n; ++i) {

            while(j < n && v[][i].h >= v[][j].h) {

                q.insert(v[][j++].w);

            }

            if(!q.empty() && *q.begin() <= v[][i].w) {

                ++sum;

                auto tmp = q.upper_bound(v[][i].w);

                q.erase(--tmp);

            }

        }

        printf("%d\n", sum);

    }

    return ;

}

　提一下为什么用upper_bound并递减，因为当此处的w比队列中任意元素大时，两种查找都返回end()迭代器，此时需要递减操作，如果w是中间大小元素，lower_bound的递减就会出错，当然特判一下也可以，等价的。

巴特西

Day3-H-Alice and Bob HDU4268

最新文章

热门文章