1 条题解

  • 0
    @ 2025-5-7 23:29:02

    解题思路

    定义数据结构

    使用结构体 Card 表示一张牌,包含数值(value)和花色(suit)。
    重载比较运算符 operator<operator>,以便根据牌的数值和花色进行排序和比较。

    输入处理

    读取测试用例数量 N
    对每个测试用例,读取 Adam 和 Eve 的牌,并存储到对应的 Card 数组中。

    排序

    对 Eve 的牌进行排序,以便快速找到能胜出的最小牌。

    贪心算法

    遍历 Adam 的每张牌,尝试找到 Eve 的牌中能胜出且未被使用的最小牌。
    如果找到这样的牌,则 Eve 得 1 分,并标记该牌为已使用。

    输出结果

    对每个测试用例,输出 Eve 的得分。

    代码实现

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <map>
    
    using namespace std;
    
    // 定义牌的结构
    struct Card {
    	char value;
    	char suit;
    	
    	// 比较函数,先比较数值,再比较花色
    	bool operator<(const Card& other) const {
    		static const string values = "23456789TJQKA";
    		static const string suits = "CDSH";
    		
    		int val1 = values.find(value);
    		int val2 = values.find(other.value);
    		if (val1 != val2) {
    			return val1 < val2;
    		}
    		
    		int suit1 = suits.find(suit);
    		int suit2 = suits.find(other.suit);
    		return suit1 < suit2;
    	}
    	
    	// 显式定义 operator>
    	bool operator>(const Card& other) const {
    		return other < *this;
    	}
    };
    
    int main() {
    	int N;
    	cin >> N;
    	
    	while (N--) {
    		int k;
    		cin >> k;
    		
    		vector<Card> adam(k);
    		vector<Card> eve(k);
    		
    		// 读取Adam的牌
    		for (int i = 0; i < k; ++i) {
    			cin >> adam[i].value >> adam[i].suit;
    		}
    		
    		// 读取Eve的牌
    		for (int i = 0; i < k; ++i) {
    			cin >> eve[i].value >> eve[i].suit;
    		}
    		
    		// 对Eve的牌进行排序
    		sort(eve.begin(), eve.end());
    		
    		int eveScore = 0;
    		vector<bool> used(k, false);
    		
    		// 遍历Adam的牌,为每张Adam的牌找到Eve的最优应对牌
    		for (int i = 0; i < k; ++i) {
    			int bestIndex = -1;
    			for (int j = 0; j < k; ++j) {
    				if (!used[j] && eve[j] > adam[i]) {
    					if (bestIndex == -1 || eve[j] < eve[bestIndex]) {
    						bestIndex = j;
    					}
    				}
    			}
    			
    			if (bestIndex != -1) {
    				eveScore++;
    				used[bestIndex] = true;
    			}
    		}
    		
    		cout << eveScore << endl;
    	}
    	
    	return 0;
    }
    

    代码解释

    结构体定义

    Card 结构体:包含两个字段 valuesuit,分别表示牌的数值和花色。
    重载了 operator<operator>,用于比较两张牌的大小。比较规则是先比较数值,数值大的牌胜出;如果数值相同,则比较花色。

    输入处理

    读取测试用例数量 N
    对每个测试用例,读取 Adam 和 Eve 的牌。Adam 的牌按顺序存储,Eve 的牌存储在另一个数组中。

    排序

    使用 std::sort 对 Eve 的牌进行排序,以便快速找到能胜出的最小牌。

    寻找最优应对牌

    遍历 Adam 的每张牌,尝试找到 Eve 的牌中能胜出且未被使用的最小牌。
    如果找到这样的牌,则 Eve 得 1 分,并标记该牌为已使用。

    输出结果

    对每个测试用例,输出 Eve 的得分。

    • 1

    信息

    ID
    1063
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者