Alice and Bob
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2571 Accepted Submission(s): 828
Problem Description
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.
Please pay attention that each card can be used only once and the cards cannot be rotated.
Input
The 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.
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.
Output
For each test case, output an answer using one line which contains just one number.
Sample Input
2
2
1 2
3 4
2 3
4 5
3
2 3
5 7
6 8
4 1
2 5
3 4
Sample Output
1
2
题意:
首先给出样例个数 T(1 ~ 50),每个样例给出 N (<= 100000)张牌,代表 Alice 和 Bob 各有 N 张牌,每张牌都有长(1 ~ 10 ^ 9)和宽(1 ~ 10 ^ 9),现要用 Alice 的牌去覆盖 Bob 的,必须长和宽都大于等于才能覆盖,问能够覆盖的最大数。
思路:
贪心 + multiset。与昨天的多校贪心题类似,先对牌统一按长由大到小排序,后用 Bob 的牌去匹配 Alice 的牌,选出 Alice 牌中长大于 Bob 长的牌,将宽放入 multiset 中,在从中选出在里面的牌中大于或者等于 Bob 牌的宽的第一个数,运用 upper_bound,之后从 multiset 中删去这张牌即可。用 multiset 的原因是可能宽度会有重复的。寻找的时候统计个数就好了。
lower_bound 返回的是第一个大于或者等于 num的数,若全部都小于则返回 end;
upper_bound 返回的是第一个大于 num 的数,若全部都小于则返回 end。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; const int MAX = 100005; typedef struct { int l, w; } node; node a[MAX], b[MAX]; bool cmp (node a, node b) { if (a.l != b.l) return a.l > b.l; return a.w > b.w; } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d%d", &a[i].l, &a[i].w); } for (int i = 0; i < n; ++i) { scanf("%d%d", &b[i].l, &b[i].w); } sort(a, a + n, cmp); sort(b, b + n, cmp); int m = 0, ans = 0; multiset<int> s; for (int i = 0; i < n; ++i) { while (m != n && a[m].l >= b[i].l) { s.insert(a[m].w); ++m; } multiset<int>::iterator it; it = s.lower_bound(b[i].w); if (it != s.end() && *it >= b[i].w) { ++ans; s.erase(it); } } printf("%d\n", ans); } }
相关推荐
Multiset ( 1 , 2 , 3 ) + Multiset ( 3 , 4 , 5 ) // == Multiset(1, 2, 3, 3, 4, 5) // Difference Multiset ( 1 , 2 , 3 ) - Multiset ( 2 , 3 ) // == Multiset(1) // Intersection Multiset ( 1 , 2 , 3 ) & ...
通过实例介绍了 cast(multiset() as) 的使用方法,以处理嵌套表的操作
stl容器multiset的使用 包含6.0代码 以及详细的文档说明
MultiSet是一款界面简洁的自动程序安装工具。不需要编写程序,用这个程序可以是你从大量的程序安装过程中解放出来。并且可以在安装过程中实现注册信息的输入 Almeza MultiSet Pro 7.8.1绿色版 自动程序安装
安装说明:安装后先不要立即运行Almeza MultiSet,将内附的“activate_multiset.amltkey”文件复制到C:\Program Files\Almeza\MultiSet目录下面即是正式版。点击菜单View-->Language-->在General中选择...
全自动软件安装,省去你安装软件的时间和烦恼
Almeza MultiSet可通过软件安装管理器将常用程序集成到一起,它先录制软件的安装过程,下次安装同一软件时就会采用“回放”的方式... 小提示:如果需要将MultiSet中的所有程序安装到位,那么直接选择“安装所有”即可
python库,解压后可用。 资源全名:multiset_multicover-0.4-cp37-cp37m-win_amd64.whl
让你从软件安装中解放,让你从此一键安装千万软件 让你从软件安装中解放,让你从此一键安装千万软件
NULL 博文链接:https://zhang-zling.iteye.com/blog/327409
Almeza MultiSet Pro 是一个自动安装程序用一个简单和方便的接口。很多时候,它需要花费大量的时间,用户在安装操作系统后,安装必要的程序。并在同一时间,用户需要更换光盘的CD-ROM和DVD-ROM驱动器,输入注册数据...
STL_multiset 方法:multisetst; 定义了一个multiset变量st,st里面可以存放T类型数据,并且能自动排序。开始st为空 排序规则:表达式”a<b为true,则a排在b前面 可用的方法 目的 格式 添加元素 st.insert ...
python库,解压后可用。 资源全名:multiset_multicover-0.2-cp310-cp310-win32.whl
主要介绍了C++ STL入门教程第七篇,multimap一对多索引,multiset多元集合的使用方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
解压即可使用 博文链接:https://heisetoufa.iteye.com/blog/368622
Java中的多集您只需要一个文件: : 因为我使用的是SpotBugs,所以有spotbugs-annotations-3.1.0.jar。 但是您也可以删除这些注释。 我的博客: :
一共四个doc文件,list综合实例、multimap和map的实例、set和multiset的综合实例、vector综合实例
因此,当「查询」动作和「插入/删除」动作频率相当时,更好的选择是使用「红黑树」实现使用 multiset 作为窗口,逻辑上:窗口内的元素都不满足答案要求在遍历的
STL