HDU 4268 Alice and Bob(贪心+Multiset的应用)
应用 and HDU 贪心
2023-09-11 14:15:00 时间
题意: 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; }
相关文章
- jQuery事件绑定.on()简要概述及应用
- Flutter 桌面应用开发配置与打包 Flutter Windows 桌面软件开发
- JavaScript 快速应用基本类型、window、计时器、Cookie
- Flask框架中上下文(请求上下文和应用上下文)用法详解
- ORB:新一代 Linux 应用
- Android 中如何从一个App启动另外一个App(如启动支付界面、启动地图界面、应用商场下载App等场景)
- 《Android 应用案例开发大全(第二版)》——2.9节壁纸的优化与改进
- 《Android 应用测试指南》——第1章,第1.1节简史
- 安徽出台医疗大数据应用发展实施意见
- C语言函数及数组的综合应用——儿童数学运算 and 递归求最大公约数
- Java 编程的动态性,第3部分: 应用反射--转载