hdu 4268 Alice and Bob(贪心+multiset)
2024-08-27 07:10:07
题意:卡牌覆盖,每张卡牌有高(height)和宽(width)。求alice的卡牌最多可以覆盖多少bob的卡牌
思路:贪心方法就是找h可以覆盖的条件下找w最大的去覆盖。
#include<iostream>
#include<stdio.h>
#include<set>
#include<algorithm>
using namespace std; struct Node{
int h,w;
int flag;
}node[]; bool cmp(Node a,Node b){
if(a.h!=b.h)return a.h<b.h;//升序
if(a.w!=b.w)return a.w<b.w;//升序
return a.flag>b.flag;//降序
} multiset<int>mt;
multiset<int>::iterator it; int main(){
int t,n,i,ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=;i<=n;++i){
scanf("%d%d",&node[i].h,&node[i].w);
node[i].flag=;
}
for(i=n+;i<=*n;++i){
scanf("%d%d",&node[i].h,&node[i].w);
node[i].flag=;
}
sort(node+,node++*n,cmp);
mt.clear();
ans=;
for(i=;i<=*n;++i){
if(node[i].flag==)mt.insert(node[i].w);
else{
if(!mt.empty()){
it=mt.begin();
if(node[i].w>=(*it)){
++ans;
it=mt.upper_bound(node[i].w);//指向键值> key的第一个元素。
--it;//指向键值<= key的第一个元素。
mt.erase(it);
}
}
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- jQuery之ajax错误调试分析
- mysql复制一列到另一列
- GWAS Simulation
- python笔记-调用eval函数出现invalid syntax错误
- 使用库函数API和C代码中嵌入汇编代码两种方式使用同一个系统调用
- 关于SVN删除后的文件不能重新添加(正常途径不行)
- Hadoop学习总结之三:Map-Reduce入门
- 转:单片机C语言中的data,idata,xdata,pdata,code
- Spring (一) IOC ( Inversion Of Control )
- javascript (十二)对象二
- mac 下安装oh my zsh
- webpack 相关资料
- JS——基础知识(三)
- 什么是测试开发工程师-google的解释
- Obj-C 实现 QFileDialog函数
- MongoDB对应SQL语句
- 用html+css+js做打地鼠小游戏
- java反射机制的简单使用
- .NET并行计算和并发8:硬件支持
- MySQL软件基本管理
热门文章
- [转]UITableView全面解析
- Linux 下tomcat的配置
- poj 3461 hash解法
- HUNAN -11566 Graduation Examination(找规律)
- Django 中的时间处理
- http://www.yiibai.com/java8/java8_temporaladjusters.html
- jquery提示消息,简单通用
- [转]JAVA集合
- [Javascript] Convert a Callback-Based JavaScript Function to a Promise-Based One
- Excel实用技巧-如何批量提取excel工作表名称