程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4268 Alice and Bob(貪心+multiset)

HDU 4268 Alice and Bob(貪心+multiset)

編輯：關於C++

HDU 4268

題意：Alice與Bob在玩卡片游戲，他們每人有n張卡片，若Alice的一張卡片長與寬都不小於Bob的一張卡片，則Bob的卡片就會被蓋住，一張卡片只可以使用一次，且不可旋轉求Alice最多可以蓋住多少張Bob的卡片。

思路：記錄兩人卡片情況，並按照長度將兩人卡片分別降序排序。遍歷兩人的卡片，將長度小於Alice的卡片長度的Bob卡片的寬度插入multiset中，在multiset中找到小於等於Alice卡片寬度的第一個數，將這個數給消去且答案+1.//貪心法自行發揮即可。

code：

/*
* @author Novicer
* language : C++/C
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double eps(1e-8);
typedef long long lint;

//const int maxn = 2*100000 + 5;
multisetBob;
//multisetAlice;

struct card{
	int x,y;
};
bool cmp(card a, card b){
	if(a.x != b.x) return a.x < b.x;
	else return a.y < b.y;
}
card al[100005],bo[100005];

int n;
int main(){
	freopen(input.txt,r,stdin);
	int T;
	cin >> T;
	while(T--){
		cin >> n;
		for(int i = 1 ; i <= n ; i++){
			scanf(%d%d,&al[i].x,&al[i].y);
			
		}
		for(int i = 1 ; i <= n ; i++){
			scanf(%d%d,&bo[i].x,&bo[i].y);
		}
		sort(al+1 , al+n+1 , cmp);
		sort(bo+1 , bo+n+1 , cmp);
//		cout << al[1].x << al[1].y << endl;
		Bob.clear();
		multiset::iterator it;
		int ans = 0;
		for(int i = 1,j = 1 ; i <= n ; i++){
			for(  ; j <= n ; j++){
				if(al[i].x >= bo[j].x) Bob.insert(bo[j].y);
				else break;
			}
//			cout << Bob.size() << endl;
			if(Bob.empty()) continue;
            
			it = Bob.lower_bound(al[i].y);
			if(it != Bob.begin()) it--;
			if(*it <= al[i].y){
                ans++;
                Bob.erase(it);
			}
        }
		cout << ans << endl;
	}
	return 0;
}