题意：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;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
悠然享受和大自然融合之乐。
