大致题意:
alice和bob每个人各有n张卡片,每张卡片都有自己的长和宽。现在规定对于alice的一张卡片a,和bob的一张卡片b。如果a的长和宽都大于等于b,则a可以覆盖b。每张卡片都只能覆盖和被覆盖一次。求alice用手中的卡片最多能覆盖多少bob的卡片。
大致思路:
贪心+各种数据结构。
贪心的策略是,从小到大枚举alice的每张卡片,每次都在bob的卡片中,挑出边长小于当前卡片的所有卡片。然后再在这些卡片中选出宽最小的可以被当前卡片覆盖的卡片。
multiset的lower_bound函数请参见 http://blog.csdn.net/niushuai666/article/details/6734650
#include<utility>
#include<cstdio>
#include<vector>
#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
const int nMax=100100;
pair<int,int>app[nMax];pair<int,int>bpp[nMax];
multiset<int> stt;
int main() {
int t,n,i,j,a,b,c,ans;
scanf("%d",&t);
while(t--)
{
stt.clear();
ans=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&app[i].first,&app[i].second);
}
for(i=0;i<n;i++)
{
scanf("%d%d",&bpp[i].first,&bpp[i].second);
}
sort(app,app+n);
sort(bpp,bpp+n);
int bpos=0;
for(i=0;i<n;i++)
{
while(bpos<n&&bpp[bpos].first<=app[i].first)
{
stt.insert(bpp[bpos].second);
bpos++;
}
if(stt.size()>=1)
{
multiset<int>::iterator it = stt.lower_bound(app[i].second);
if(it==stt.end())it--;
if(it!=stt.begin()&&*it>app[i].second)it--;
if (*it <= app[i].second ) {
stt.erase(it);
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
STL_multiset 方法:multisetst; 定义了一个multiset变量st,st里面可以存放T类型数据,并且能自动排序。开始st为空 排序规则:表达式”a<b为true,则a排在b前面 可用的方法 目的 格式 添加元素 st.insert ...
> = C ++ 11 支持的容器或类似容器的类型: std :: pair std :: tuple std :: array std :: deque std :: forward_list std :: initializer_list std :: list std :: vector std :: set std :: multiset std :...
Chapter 23: Associative Containers–set, multiset, map and multimap 559 Chapter 24: Bit Sets 578 Chapter 25: Algorithms 589 REFERENCES 625 APPENDIX–A ASCII CHARACTER CODE SET 627 APPENDIX–B C++ ...
通过实例介绍了 cast(multiset() as) 的使用方法,以处理嵌套表的操作
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 ) & ...
stl容器multiset的使用 包含6.0代码 以及详细的文档说明
安装说明:安装后先不要立即运行Almeza MultiSet,将内附的“activate_multiset.amltkey”文件复制到C:\Program Files\Almeza\MultiSet目录下面即是正式版。点击菜单View-->Language-->在General中选择...
MultiSet是一款界面简洁的自动程序安装工具。不需要编写程序,用这个程序可以是你从大量的程序安装过程中解放出来。并且可以在安装过程中实现注册信息的输入 Almeza MultiSet Pro 7.8.1绿色版 自动程序安装
Almeza MultiSet可通过软件安装管理器将常用程序集成到一起,它先录制软件的安装过程,下次安装同一软件时就会采用“回放”的方式... 小提示:如果需要将MultiSet中的所有程序安装到位,那么直接选择“安装所有”即可
multiset.cr:Crystal中的多集(袋)实现
python库,解压后可用。 资源全名:multiset_multicover-0.4-cp37-cp37m-win_amd64.whl
proirity_queue性能分析源码 比较了三种queue:std::multimap、std::multiset、std::priority_queue 的性能
让你从软件安装中解放,让你从此一键安装千万软件 让你从软件安装中解放,让你从此一键安装千万软件
Java中的多集您只需要一个文件: : 因为我使用的是SpotBugs,所以有spotbugs-annotations-3.1.0.jar。 但是您也可以删除这些注释。 我的博客: :
NULL 博文链接:https://zhang-zling.iteye.com/blog/327409
python库,解压后可用。 资源全名:multiset_multicover-0.2-cp310-cp310-win32.whl
Almeza MultiSet Pro 是一个自动安装程序用一个简单和方便的接口。很多时候,它需要花费大量的时间,用户在安装操作系统后,安装必要的程序。并在同一时间,用户需要更换光盘的CD-ROM和DVD-ROM驱动器,输入注册数据...
第一周 Group Fluo 在奥胡斯大学 AWP 课程第一周的作业 ... Multiset:在浏览器中运行 html/MultiSet.html 冰淇淋店:在浏览器中运行 html/icecream_shop.html Klotski:在浏览器中运行 html/klotski.html
全自动软件安装,省去你安装软件的时间和烦恼
因此,当「查询」动作和「插入/删除」动作频率相当时,更好的选择是使用「红黑树」实现使用 multiset 作为窗口,逻辑上:窗口内的元素都不满足答案要求在遍历的