題意：Alice和Bob都有N個矩形，問Alice的矩形最多能覆蓋Bob的矩形多少個。每個矩形只能用一次，寬與高不能旋轉。 ——>>貪心，剛開始想到的策略是：將矩形按寬與高從大到小排序，然後Alice用最寬的去蓋Bob的力所能及的最寬的，結果WA啦，現在發現，方向反了！貪心的策略應是從小到大，讓Alice的每個矩形都能發揮其最大價值，即：取其中一維：寬度，從小到大來訪問，每訪問一個，在高度中從小到大搜出所有滿足的高度，蓋掉力所能及的最大的那個（multiset中有查找函數upper_bound(x)，返回第一個大於x的迭代器）。第一次用pair與multiset，滋味不錯～～ [cpp] #include <cstdio> #include <vector> #include <set> #include <algorithm> using namespace std; typedef pair<int, int> pii; const int maxn = 100000 + 10; int main() { int T, N, i, j, h, w; scanf("%d", &T); while(T--) { scanf("%d", &N); vector<pii> A, B; for(i = 0; i < N; i++) { scanf("%d%d", &h, &w); A.push_back(make_pair(h, w)); } for(i = 0; i < N; i++) { scanf("%d%d", &h, &w); B.push_back(make_pair(h, w)); } sort(A.begin(), A.end()); sort(B.begin(), B.end()); int cnt = 0; multiset<int> s; s.clear(); for(i = 0, j = 0; i < N; i++) { while(j < N && A[i].first >= B[j].first) s.insert(B[j++].second); if(!s.empty()) www.2cto.com { multiset<int>::iterator p = s.upper_bound(A[i].second); if(p != s.begin()) { s.erase(--p); cnt++; } } } printf("%d\n", cnt); } return 0; }
