Alice and Bob HDU

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

爱丽丝和鲍勃的游戏永远不会结束。今天，他们推出了一款新游戏。在这场比赛中，他们两人分别拥有N张不同的矩形牌。爱丽丝想用他的卡片来掩护鲍勃的。如果A的高度不小于B并且A的宽度不小于B，则卡A可以覆盖卡B.作为最好的程序员，要求您计算Alice可以覆盖的鲍勃卡的最大数量。
请注意，每张卡只能使用一次，卡不能旋转。

通过这题学习了一个新的数据结构multiset

这个数据结构完美的切合题目意思

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<queue>

 #include<math.h>

 #include<set>

 using namespace std;

 struct node

 {

     int w,h;

 }a[],b[];

 int cmp(node c,node d)

 {

     return c.w<d.w;

 }

 multiset<int>m;

 multiset<int>::iterator it;

 int main() {

     int t;

     scanf("%d",&t);

     while(t--){

         int n;

         scanf("%d",&n);

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

             scanf("%d%d",&a[i].w,&a[i].h);

         }

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

             scanf("%d%d",&b[i].w,&b[i].h);

         }

         int ans=;

         sort(a,a+n,cmp);

         sort(b,b+n,cmp);

         m.clear();

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

             while(j<n&&a[i].w>=b[j].w) {

                 m.insert(b[j++].h);

             }

             if(m.empty()) continue;

             it = m.upper_bound(a[i].h);

             if(it != m.begin()) {

                 it--;

                 m.erase(it);

                 ans++;

             }

         }

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

     }

     return ;

 }

巴特西

Alice and Bob HDU - 4268

最新文章

热门文章