e557 - 11678 - Cards' Exchange

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Alice 和 Betty 各自擁有一組寶可夢卡牌，卡牌的 ID 以整數表示。他們可以進行卡牌交換，每次交換需要交換相同數量的卡牌，且交換的卡牌不能重複。題目要求計算 Alice 和 Betty 最多可以交換的卡牌數量。

解題思路

解題思路是統計 Alice 和 Betty 各自擁有的卡牌種類。然後，找出兩者共同擁有的卡牌種類，將這些卡牌種類的數量從各自的統計中減去。最後，Alice 和 Betty 各自剩下的卡牌種類數量中，取較小值，即為他們可以交換的最大卡牌數量。這個方法基於貪心策略，盡可能多地消除共同擁有的卡牌，以最大化交換數量。

複雜度分析

• 時間複雜度: O(N + M + K)，其中 N 是 Alice 的卡牌數量，M 是 Betty 的卡牌數量，K 是卡牌 ID 的最大值。主要時間花在統計卡牌數量和計算剩餘卡牌數量上。
• 空間複雜度: O(K)，其中 K 是卡牌 ID 的最大值。主要空間花在儲存卡牌數量統計陣列上。

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,b;
	while(cin >> a >> b){
		if(a==0&&b==0)break;
		int x[100001]={0},y[100001]={0},t,xa=0,ya=0;
		while(a--){
			cin >> t;
			++x[t];
		}
		while(b--){
			cin >> t;
			++y[t];
		}
		for(int i=0;i<100001;++i){
			if(x[i]&&y[i]){
				x[i]=0;
				y[i]=0;
			}
		}
		for(int i=0;i<100001;++i){
			if(x[i])
				++xa;
			if(y[i])
				++ya;
		}
		cout << min(xa,ya) << "\n";
	}
}