题意: 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;
}

最新文章

  1. swift相关
  2. modelsim搭建uvm环境及实例
  3. Maven仓库管理-Nexus
  4. arcmap Command
  5. 【BZOJ-3626】LCA 树链剖分
  6. django笔记-模型数据模板呈现过程记录(多对多关系)
  7. javascript优化--12模式(设计模式)03
  8. 查看数据库磁盘使用多少G:
  9. ORACLE 数据块dump
  10. CentOS安装keepalived
  11. 链表操作,空间复杂度要求为O(1)
  12. input失效后,怎么改变它默认就有的灰色
  13. (UE4) 动态加载DLL
  14. 3390: [Usaco2004 Dec]Bad Cowtractors牛的报复
  15. 基于Intranet的零件库管理信息系统设计--part02
  16. 阿里云Centos7.x MySql安装教程示例
  17. 时间插件datepicker(jQuery-UI,bootstrap)和jquery-steps的冲突解决。。。
  18. idea spring-boot总结
  19. [git] 文件操作
  20. HD-SDI制式学习

热门文章

  1. Adding a model
  2. nyoj--973--天下第一(SPFA判断负环)
  3. VisoStudio 允许局域网联机调试网站
  4. Python笔记(十)——操作SQLServer
  5. hdu 3729 最大匹配
  6. Spring aop(实验写法)
  7. ACM___数学___九的余数
  8. QS之vsim
  9. vim 常用操作笔记
  10. redis启动出错 Creating Server TCP listening socket 127.0.0.1:6379: bind: No error解决办法