题解 CF1191B 【Tokitsukaze and Mahjong】

· · 题解

题目大意

本人不会玩麻将，所以翻译尽可能按照题面来

这是日式麻将的一种衍生版。

一张麻将牌由一种类型（ m,p,s ）和一个数字（ 1,2,...,9 ）组成。类型为 p ，数字为 4 的牌表示为 4p 。

一开始你手中有三张牌。每次你会抽一张牌，这张牌可以是任意一张合法的麻将牌（和手中已有的牌一样也可以）。你可以抽任何一张你想要的牌。

要赢得这个游戏，你手中至少要有一个 mentsu 。

一个 mentsu 由一个 koutsu 或 一个 shuntsu 组成。 koutsu 就是三张完全一样的牌。 shuntsu 就是三张类型一样，数字 连续 的三张牌。（和你手中牌的顺序无关，只要有三张牌构成这一类型即可）

给出一开始你手中的三张牌，问你最少还要抽多少张牌才能赢。

解题思路

有一种用二维数组的解法。

我们用一个二维数组 tf[i][j] 表示数字为 i ，类型为 j 的牌在初始手牌中的出现次数。我们不必对每种类型的牌确定一个对应的编号，由于输入的是字符类型，我们可以开一个 128\times 128 的数组在存储。

首先我们考虑用手中的牌构成 koutsu 的情况，我们找到 tf[i][j] 的最大值，这就是手牌中最多相同的牌数。要构成 koutsu 而胜利，最优的方法就是把这张牌补到三张，这样的答案就是 3-\max\{tf[i][j]\} 。

接下来考虑构成 shuntsu 的情况。 shuntsu 的要求是三张类型相同的牌，数字连续。我们枚举相同的类型 j ，接着枚举 shuntsu 中最小的数字，需要补全的最小牌数为 3- 从最小的数字开始连续的三个位置有多少个 tf=0 。

上面的写法要 处理边界条件 。本人的写法是判断相同类型连续的数字有多少个，用 3 减去这个值计入答案，并特判形如 2m~4m 的两张牌，只需补一张 3m 即可的情况。

代码展示

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=5;
int ans,maxx;
char s[maxn][maxn];
int tf[128][128];
int main()
{
    for(int i=1;i<=3;i++)scanf(" %c%c",s[i]+1,s[i]+2),tf[(int)s[i][1]][(int)s[i][2]]++;
    for(int i=0;i<128;i++)for(int j=0;j<128;j++)maxx=max(maxx,tf[i][j]);
    ans=3-maxx;
    for(int j=0;j<128;j++)
    {
        maxx=0;
        for(int i=0;i<128;i++)
        {
            if(tf[i][j])maxx++;
            else maxx=0;
            ans=min(ans,3-maxx);
            if(i-2>=0&&tf[i][j]&&tf[i-2][j])ans=min(ans,1);
        }
    }
    printf("%d\n",ans);
    return 0;
}