自动搬运

查看原文

来自洛谷，原作者为

	昒昕 我追逐的泡沫，原来如此沉重 || QQ：3432735604

搬运于2025-08-24 22:33:47，当前版本为作者最后更新于2021-11-07 18:43:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更新了数据，卡掉了暴力做法，在此表示歉意。

做法 1

贪心+桶排，时间复杂度 $\mathcal{O}(n)$

对于一个牌点，一对“小昕昕”是优先把 牌最少的花色 配 牌最多的花色。

也就是对于某一牌点，优先拿 $1$ 张牌的花色与 $2$ 张牌的花色配对，如果没有 $1$ 张牌的花色，才可以把 $2$ 张牌的花色拆开。

所以就想到了桶排。

#include <cstdio>

int poke[6][21];
int ans;

int change_color(char p) {
    switch (p) {
        case 'S': return 1;
        case 'H': return 2;
        case 'C': return 3;
        case 'D': return 4;
    }
}
int change_num(char p) {
    switch (p) {
        case 'A': return 1;
        case 'T': return 10;
        case 'J': return 11;
        case 'Q': return 12;
        case 'K': return 13;
        default: return int(p-'0');
    }
}
int main() {
//  freopen("xinxin.in","r",stdin);
//  freopen("xinxin.out","w",stdout);
    int n;
    char c,num;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf(" %c%c",&c,&num); //空格是为了吃前面的回车
        poke[change_color(c)][change_num(num)]++; //相应的牌个数加1
    }
    for (int i=1;i<=13;i++) //13个牌点
        for (int j=1;j<=4;j++) //4个花色
            for (int k=1;k<=4;k++)
                if (poke[j][i]==2&&poke[k][i]==1&&j!=k) { //正好是1-2的配对
                    poke[j][i]=0;
                    poke[k][i]=0;
                    ans++;
                }

    for (int i=1;i<=13;i++)
        for (int j=1;j<=4;j++)
            for (int k=1;k<=4;k++)
                if (poke[j][i]==2&&poke[k][i]!=0&&j!=k) { //如果这两个花色都是两张，那么只能拆其中一个花色，给另一个花色配
                    poke[j][i]=0;
                    poke[k][i]--;
                    ans++;
                }
    printf("%d\n",ans);
    return 0;
}

做法 2

桶排+找规律，时间复杂度 $\mathcal{O}(n \log n)$

想一想，一共有 $2$ 副无大小王的扑克牌，说明每个花色至多有 $2$ 张牌。

由于不同牌点间相互不影响，所以单从一个牌点考虑，并且无视花色。

• 如果该牌点如果共有 $1$ 或 $2$ 张牌，肯定无法组成“小昕昕”。
• 如果有 $3$ 或 $4$ 张牌，$0$ 对或 $1$ 对“小昕昕”都有可能，所以需要依靠花色判断。
• 如果有 $5$ 张牌，只有 $2-1-1-1$ 或 $2-2-1-0$ 的情况，最多能配 $1$ 对。
• 如果有 $6$ 张牌，有 $2-2-2$ 和 $2-2-1-1$ 的情况，都是 $2$ 对。
• 如果有 $7$ 或 $8$ 张牌，则分别是 $2-2-2-1$ 和 $2-2-2-2$ 的情况，$2$ 对。

• 再来考虑 $3$ 张牌，有 $1-1-1-0$ 和 $2-1-0-0$ 的情况，花色分别是 $3$ 种和 $2$ 种，如果花色有两种，就是 $1$ 对小昕昕。
• $4$ 张牌也同理，最多配 $1$ 对“小昕昕”。

#include <bits/stdc++.h>
using namespace std;

int change_num(char p) {
    switch (p) {
        case 'A': return 1;
        case 'T': return 10;
        case 'J': return 11;
        case 'Q': return 12;
        case 'K': return 13;
        default: return int(p-'0');
    }
}

int n,ans;
set <char> color[14];
int cnt[14]; //存储每个牌点的数量，无视花色

int main() {
//  freopen("xinxin.in","r",stdin);
//  freopen("xinxin.out","w",stdout);
    char a,b;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
    	scanf(" %c%c",&a,&b);
    	int t=change_num(b);
    	cnt[t]++; //该牌点的数量增加
    	color[t].insert(a); //保存花色，以判断3张或4张牌的情况
	}
	for (int i=1;i<=13;i++) {
		if (cnt[i]==5) ans++; //5张1对
		else if (cnt[i]>=6) ans+=2; //6,7,8张2对
		else if (cnt[i]>=3&&cnt[i]<=4&&(int)color[i].size()!=cnt[i]) ans++;
        //如果是3,4张，则看总花色数
        //如果3张牌共有3个不同的花色 或 4张牌共有不同的4个花色，肯定不能组成“小昕昕”
	}
	printf("%d\n",ans);
   return 0;
}