扑克牌again

又打牌

问题描述

打牌新规则：
👉所有扑克牌只按数字来算大小，忽略花色。
👉每张扑克牌的大小由一个值表示。A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K 分别指代 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13。
👉每个玩家抽得 5 张扑克牌，组成一手牌。(每种扑克牌的张数是无限的)

一手牌有不同类型，并且有大小之分。
比如一手牌 α, β，要么 α > β，要么 α < β，要么 α = β。

对于不同类型的一手牌，其值的大小即下面的标号；对于同类型的一手牌，根据组成这手牌的 5 张牌不同，其值不同。下面依次列举了这手牌的形成规则：

1. 大牌：这手牌不符合下面任一个形成规则。如果 α 和 β 都是大牌，那么定义它们的大小为组成这手牌的 5 张牌的大小总和。
2. 对子：5 张牌中有 2 张牌的值相等。如果 α 和 β 都是对子，比较这个 “对子” 的大小，如果 α 和 β 的 “对子” 大小相等，那么比较剩下 3 张牌的总和。
3. 两对：5 张牌中有两个不同的对子。如果 α 和 β 都是两对，先比较双方较大的那个对子，如果相等，再比较双方较小的那个对子，如果还相等，只能比较 5 张牌中的最后那张牌组不成对子的牌。
4. 三个：5 张牌中有 3 张牌的值相等。如果 α 和 β 都是 “三个”，比较这个 “三个” 的大小，如果 α 和 β 的 “三个” 大小相等，那么比较剩下 2 张牌的总和。
5. 三带二：5 张牌中有 3 张牌的值相等，另外 2 张牌值也相等。如果 α 和 β 都是 “三带二”，先比较它们的 “三个” 的大小，如果相等，再比较 “对子” 的大小。
6. 炸弹：5 张牌中有 4 张牌的值相等。如果 α 和 β 都是 “炸弹”，比较 “炸弹” 的大小，如果相等，比较剩下那张牌的大小。
7. 顺子：5 张牌中形成 x, x+1, x+2, x+3, x+4。如果 α 和 β 都是 “顺子”，直接比较两个顺子的最大值。
8. 龙顺：5 张牌分别为 10、J、Q、K、A。

要求输出一个排行榜。排行榜按照选手们的 “一手牌” 大小进行排序，如果两个选手的牌相等，那么人名字典序小的排在前面。

Input

输入包含多组数据。每组输入开头一个整数 n (1 ≤ n ≤ 100000)，表明全场共多少人。
随后是 n 行，每行一个字符串 s1 和 s2 (1 ≤ |s1|,|s2| ≤ 10)， s1 是对应人的名字，s2 是他手里的牌情况。

Output

对于每组测试数据，输出 n 行，即这次全场人的排名。

Sample

Input: 
3
DongDong AAA109
ZJM 678910
Hrz 678910

Output: 
Hrz
ZJM
DongDong

Limitation

Time limit		1000 ms
Memory limit	262144 kB

解题思路

又是打牌，又是又臭又长的题干，又是中间麻烦的字符串处理过程……这种题目不算难，就是要反复读题，中间处理过程多检查几遍，不然容易WA。

分步处理

长题可以分成多步骤解决，这题的主要步骤就是：

1. 手牌字符串转整型数组，并排序
2. 根据题意判断手牌牌型，并记录第 n 关键字(第一关键字是牌型的编号)，存到结构体内
   2.1 大牌：啥也不是，第二关键字是5张牌的和
   2.2 对子：2等3不等，第二关键字是这个”2”，第三关键字是这个3张牌的和
   2.3 两对：2等+2等+1，第二关键字是大的”2”，第三关键字是较小的”2”，第四关键字是这个”1”
   2.4 三个：3等2不等，第二关键字是这个”3”，第三关键字是这个2张牌的和
   2.5 三带二：3等+2等，第二关键字是这个”3”，第三关键字是这个”2”
   2.6 炸弹：4等+1，第二关键字是这个”4”，第三关键字是这个”1”
   2.7 顺子：形如”1 2 3 4 5””A B C D E”，第二关键字是这个”5”(“E”)
   2.8 龙顺：手牌为10、J、Q、K、A，即数组[1, 10, 11, 12, 13]
3. 将所有人的手牌排序，输出人名

逐个攻破

整体思路清晰后，就一一实现：

String转int Array[]：对于10特殊处理，扫到 ‘10’ 的 ‘1’ 就存入10，对于 ‘10’ 的 ‘0’ 不做处理，因为扫不到其它的 1 (A、J、Q、K)。

判断牌型：用一个int sameCnt记录相同牌有几张(用 a_i 跟 a_i+1 对比，所以sameCnt = 各组相同张数和 - 1)，并用一个vector<int>存放相同牌，然后可依此大致分为3大组：

Type	Sample	sameCnt	vector
对子	[[A A] B C D] [B [A A] C D] [B C [A A] D] [B C D [A A]]	1	[A]
两对	[[A A] [B B] C] [[A A] C [B B]] [C [A A] [B B]]	2	[A, B]
三个	[[A A A] B C] [B [A A A] C] [B C [A A A]]	2	[A, A]
三带二	[[A A A] [B B]] [[B B] [A A A]]	3	[A, A, B] [B, A, A]
炸弹	[[A A A A] B] [B [A A A A]]	3	[A, A, A]
顺子	[x, x+1, x+2, x+3, x+4]	0	EMPTY
龙顺	[1, 10, 11, 12, 13]	0	EMPTY
大牌	[A B C D E]	0	EMPTY

每个大组里根据vector就可以把牌型再细分出来了，同时记录第 n 关键字。(详见代码)

心得

自己随便出几组数据测试没啥问题，不过提交还是WA了，所以仔细再读了题目，发觉也没漏了啥条件，再反复看看了代码，利用中间输出，测试是哪一大步出错了？测了测也没啥错误啊……

找了好久才发现判断大牌的for循坏条件把i < 5写成i < 4……因为前面算sameCnt的时候条件是i < 4，我貌似直接 copy-paste 了……

源代码

#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

struct poker {
	string name;
	int theLevel;
	int firstKey, secondKey, thirdKey;
	poker(string na, int lvl, int fK, int sK, int tK): name(na),
		theLevel(lvl), firstKey(fK), secondKey(sK), thirdKey(tK) { }
};

poker level(string name, vector<int> p) {
	int sameCnt = 0;
	vector<int> v;
	for (int i = 0; i < 4; i++) {
		if (p[i] == p[i + 1]) {
			sameCnt++;
			v.push_back(p[i]);
		}
	}

	// (2) 2 of 5 is equal
	if (sameCnt == 1) {
		int firstKey = v.at(0);
		int secondKey = 0;
		for (int i = 0; i < 5; i++)
			if (p[i] != firstKey)
				secondKey += p[i];
		poker po(name, 2, firstKey, secondKey, 0);
		return po;
	}

	if (sameCnt == 2) {
		// (3) 2 and 2 of 5 each is equal
		if (v.at(0) != v.at(1)) {
			int firstKey = v.at(1);
			int secondKey = v.at(0);
			int thirdKey = 0;
			for (int i = 0; i < 5; i++)
				if (p[i] != firstKey && p[i] != secondKey)
					thirdKey = p[i];
			poker po(name, 3, firstKey, secondKey, thirdKey);
			return po;
		}

		// (4) 3 of 5 is equal
		if (v.at(0) == v.at(1)) {
			int firstKey = v.at(0);
			int secondKey = 0;
			for (int i = 0; i < 5; i++)
				if (p[i] != firstKey)
					secondKey += p[i];
			poker po(name, 4, firstKey, secondKey, 0);
			return po;
		}
	}
	
	if (sameCnt == 3) {
		// (5) 3 of 5 & 2 of 5
		if (v.at(0) != v.at(2)) {
			int firstKey = v.at(1);
			int secondKey = 0;
			if (v.at(0) != v.at(1))
				secondKey = v.at(0);
			if (v.at(0) == v.at(1))
				secondKey = v.at(2);
			poker po(name, 5, firstKey, secondKey, 0);
			return po;
		}

		// (6) 4 of 5 is equal
		if (v.at(0) == v.at(2)) {
			int firstKey = v.at(0);
			int secondKey = 0;
			if (p[0] == firstKey)
				secondKey = p[4];
			if (p[0] != firstKey)
				secondKey = p[0];
			poker po(name, 6, firstKey, secondKey, 0);
			return po;
		}
	}

	if (sameCnt == 0) {
		// (7) shunza
		if ((p[0] + 1 == p[1]) && (p[1] + 1 == p[2]) &&
			(p[2] + 1 == p[3]) && (p[3] + 1 == p[4])) {
			int firstKey = p[4];
			poker po(name, 7, firstKey, 0, 0);
			return po;
		}

		// (8) 10, J, Q, K, A
		else if (p[0] == 1 && p[1] == 10 && p[2] == 11
			&& p[3] == 12 && p[4] == 13) {
			poker po(name, 8, 0, 0, 0);
			return po;
		}

		// (1) none of above
		else {
			int firstKey = 0;
			for (int i = 0; i < 5; i++)
				firstKey += p[i];
			poker po(name, 1, firstKey, 0, 0);
			return po;
		}
	}
}

vector<int> convert(string s) {
	int size = s.size();
	vector<int> poke;

	map<char, int> pMap;
	pMap['A'] = 1;
	for (int i = 50; i <= 57; i++)
		pMap[i] = i - 48;
	pMap['1'] = 10;
	pMap['J'] = 11;
	pMap['Q'] = 12;
	pMap['K'] = 13;
	pMap['0'] = 0;

	for (int i = 0; i < size; i++) {
		int res = pMap[s[i]];
		if (res != 0)
			poke.push_back(res);
	}

	sort(poke.begin(), poke.end());

	return poke;
}

bool cmp(const poker& p1, const poker& p2) {
	if (p1.theLevel == p2.theLevel) {
		if (p1.firstKey == p2.firstKey) {
			if (p1.secondKey == p2.secondKey) {
				if (p1.thirdKey == p2.thirdKey) {
					return p1.name.compare(p2.name) < 0;
				}
				return p1.thirdKey > p2.thirdKey;
			}
			return p1.secondKey > p2.secondKey;
		}
		return p1.firstKey > p2.firstKey;
	}
	return p1.theLevel > p2.theLevel;
}

int main() {
	int n;
	while (!(cin >> n).eof()) {
		vector<poker> v;
		while (n--) {
			string s1, s2;
			cin >> s1 >> s2;
			vector<int> p = convert(s2);
			poker po = level(s1, p);
			v.push_back(po);
		}

		sort(v.begin(), v.end(), cmp);
		for (int i = 0; i != v.size(); i++)
			cout << v[i].name << endl;
	}
	return 0;
}