HDU 4268 Alice and Bob(贪心+Multiset的应用)
2024-09-06 00:36:43
题意: Alice和Bob有n个长方形,有长度和宽度,一个矩形能够覆盖还有一个矩形的条件的是,本身长度大于等于还有一个矩形,且宽度大于等于还有一个矩形。矩形不可旋转。问你Alice最多能覆盖Bob的几个矩形?
思路:贪心,先依照h将Alice和Bob的矩形排序,对于Alice的每一个矩形。假设Bob的矩形的h小于Alice的h,将Bob的w插入到集合中。
然后,在集合中找到不大于Alice矩形d的最大的Bob的d,那么这样做肯定是最优的。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
using namespace std; //const int maxn = 100 + 5;
//const int INF = 0x3f3f3f3f;
struct Card {
int h, d;
}; Card ca[100010], cb[100010];
bool cmp1(Card A, Card B) {
return A.h < B.h;
}
multiset<int> ms; int main() {
// freopen("input.txt", "r", stdin);
int t; cin >> t;
int n;
while(t--) {
cin >> n;
ms.clear();
for(int i = 0; i < n; i++) scanf("%d%d", &ca[i].h, &ca[i].d);
for(int i = 0; i < n; i++) scanf("%d%d", &cb[i].h, &cb[i].d);
sort(ca, ca+n, cmp1);
sort(cb, cb+n, cmp1);
int pos = 0, ans = 0;
for(int i = 0; i < n; i++) {
while(pos < n) {
if(ca[i].h >= cb[pos].h) {
ms.insert(cb[pos].d); pos++;
}
else break;
}
if(ms.empty()) continue;
multiset<int>::iterator it = ms.upper_bound(ca[i].d);
if(it != ms.begin()) {
ans++; ms.erase(--it);
}
}
cout << ans << endl;
}
return 0;
}
最新文章
- swift相关
- modelsim搭建uvm环境及实例
- Maven仓库管理-Nexus
- arcmap Command
- 【BZOJ-3626】LCA 树链剖分
- django笔记-模型数据模板呈现过程记录(多对多关系)
- javascript优化--12模式(设计模式)03
- 查看数据库磁盘使用多少G:
- ORACLE 数据块dump
- CentOS安装keepalived
- 链表操作,空间复杂度要求为O(1)
- input失效后,怎么改变它默认就有的灰色
- (UE4) 动态加载DLL
- 3390: [Usaco2004 Dec]Bad Cowtractors牛的报复
- 基于Intranet的零件库管理信息系统设计--part02
- 阿里云Centos7.x MySql安装教程示例
- 时间插件datepicker(jQuery-UI,bootstrap)和jquery-steps的冲突解决。。。
- idea spring-boot总结
- [git] 文件操作
- HD-SDI制式学习
热门文章
- Adding a model
- nyoj--973--天下第一(SPFA判断负环)
- VisoStudio 允许局域网联机调试网站
- Python笔记(十)——操作SQLServer
- hdu 3729 最大匹配
- Spring aop(实验写法)
- ACM___数学___九的余数
- QS之vsim
- vim 常用操作笔记
- redis启动出错 Creating Server TCP listening socket 127.0.0.1:6379: bind: No error解决办法