题解 | #小红玩纸牌#

题目链接

小红玩纸牌

题目描述

给定一副数量庞大的扑克牌，包含四种花色（'S', 'H', 'D', 'C'）和不同的数值。小红每次可以从中取出 5 张牌，如果这 5 张牌构成“同花顺”，则获得 1 分，然后将这 5 张牌丢弃。

“同花顺”是指 5 张牌花色相同，且数值是连续的（例如：5H, 6H, 7H, 8H, 9H）。

任务是计算小红最多可以获得多少分。

解题思路

这个问题的核心在于，如何选择组成的同花顺，才能使得总的得分最高。因为取出的牌会被丢弃，所以一个选择可能会影响后续的选择。例如，一张 5H 既可以用于组成 1H-5H 的同花顺，也可以用于 2H-6H 等等。

由于不同花色的牌之间不能互相组成同花顺，我们可以将问题分解：分别计算每一种花色最多能获得多少分，然后将四个花色的得分相加，即为总分。

对于单一花色，我们拥有不同数值的牌以及它们各自的数量。问题转化为：给定一系列数值和对应的牌数，如何组成最多的 5 张连续数值的牌组？

这里可以采用一种贪心策略。我们按牌的数值从小到大进行遍历。对于当前我们拥有的数值为 $v$ 的牌，我们贪心地检查是否能以它作为起始牌，形成一个 $v, v+1, v+2, v+3, v+4$ 的同花顺。

能形成多少个这样的同花顺，取决于这个序列中最少的牌的数量。例如，如果我们有 2 张 $v$ ，3 张 $v+1$ ，1 张 $v+2$ ，5 张 $v+3$ 和 4 张 $v+4$ ，那么我们最多只能形成 $\min(2, 3, 1, 5, 4) = 1$ 个以 $v$ 开头的同花顺。

优化：

一个朴素的实现是遍历从最小牌值到最大牌值的所有整数，但这在牌值范围很大但分布稀疏时会导致超时。正确的做法是只遍历我们实际拥有的牌的数值。

贪心策略的正确性：

我们从最小的数值开始，贪心地组成所有可能的同花顺。这样做是正确的，因为一个以较小数值 $v$ 开头的同花顺 (v, ..., v+4) 所使用的牌，只会与以 $v+1, v+2, v+3, v+4$ 开头的同花顺竞争资源。通过优先满足数值最小的组合，我们确保了这些“最紧急”的牌（因为它们无法参与更小数值的顺子）被优先使用，从而不会因为保留它们而错失当前的机会。这种局部最优的选择最终能导向全局最优。

算法步骤：

数据存储：使用四个 map（或哈希表）来分别存储四种花色的牌，键是牌的数值，值是数量。
按花色计算：对每一种花色，执行以下操作：

a. 获取该花色所有存在的牌的数值，并进行排序。

b. 遍历这些排好序的数值 $v$ 。

c. 对于每个 $v$ ，检查其剩余数量。如果大于 0，则计算可以组成的以 $v$ 为起点的同花顺数量 $k$ 。 $k$ 等于 $v, v+1, \dots, v+4$ 这五张牌中数量的最小值。

d. 如果 $k > 0$ ，则将总分增加 $k$ ，并从 map 中将这五种牌的数量都减去 $k$ 。
汇总：将四种花色的得分相加，得到最终答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

long long solve_suit(map<int, long long>& counts) {
    if (counts.empty()) {
        return 0;
    }
    long long score = 0;
    
    vector<int> keys;
    for (auto const& [key, val] : counts) {
        keys.push_back(key);
    }

    for (int v : keys) {
        if (counts.count(v) == 0 || counts[v] == 0) {
            continue;
        }

        long long num_flushes = counts[v];
        for (int i = 1; i < 5; ++i) {
            num_flushes = min(num_flushes, counts.count(v + i) ? counts[v + i] : 0);
        }

        if (num_flushes > 0) {
            score += num_flushes;
            for (int i = 0; i < 5; ++i) {
                counts[v + i] -= num_flushes;
            }
        }
    }
    return score;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<char, map<int, long long>> suits;
    for (int i = 0; i < n; ++i) {
        int value;
        long long count;
        char suit_char;
        cin >> value >> count >> suit_char;
        suits[suit_char][value] += count;
    }

    long long total_score = 0;
    total_score += solve_suit(suits['S']);
    total_score += solve_suit(suits['H']);
    total_score += solve_suit(suits['D']);
    total_score += solve_suit(suits['C']);

    cout << total_score << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.TreeMap;
import java.util.Arrays;

public class Main {
    public static long solveSuit(TreeMap<Integer, Long> counts) {
        if (counts.isEmpty()) {
            return 0;
        }
        long score = 0;
        
        Integer[] keys = counts.keySet().toArray(new Integer[0]);

        for (int v : keys) {
            if (counts.getOrDefault(v, 0L) == 0) {
                continue;
            }

            long numFlushes = counts.get(v);
            for (int i = 1; i < 5; i++) {
                numFlushes = Math.min(numFlushes, counts.getOrDefault(v + i, 0L));
            }

            if (numFlushes > 0) {
                score += numFlushes;
                for (int i = 0; i < 5; i++) {
                    counts.put(v + i, counts.get(v + i) - numFlushes);
                }
            }
        }
        return score;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<Character, TreeMap<Integer, Long>> suits = new TreeMap<>();
        suits.put('S', new TreeMap<>());
        suits.put('H', new TreeMap<>());
        suits.put('D', new TreeMap<>());
        suits.put('C', new TreeMap<>());

        for (int i = 0; i < n; i++) {
            int value = sc.nextInt();
            long count = sc.nextLong();
            char suitChar = sc.next().charAt(0);
            suits.get(suitChar).put(value, suits.get(suitChar).getOrDefault(value, 0L) + count);
        }

        long totalScore = 0;
        totalScore += solveSuit(suits.get('S'));
        totalScore += solveSuit(suits.get('H'));
        totalScore += solveSuit(suits.get('D'));
        totalScore += solveSuit(suits.get('C'));

        System.out.println(totalScore);
    }
}

import sys

def solve_suit(counts):
    if not counts:
        return 0
    
    score = 0
    for v in sorted(counts.keys()):
        if counts.get(v, 0) == 0:
            continue

        num_flushes = counts.get(v, 0)
        for i in range(1, 5):
            num_flushes = min(num_flushes, counts.get(v + i, 0))
        
        if num_flushes > 0:
            score += num_flushes
            for i in range(5):
                counts[v + i] -= num_flushes
    return score

def main():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        suits = {'S': {}, 'H': {}, 'D': {}, 'C': {}}
        for _ in range(n):
            line = sys.stdin.readline()
            if not line: break
            value, count, suit_char = line.split()
            value, count = int(value), int(count)
            
            current_counts = suits[suit_char]
            current_counts[value] = current_counts.get(value, 0) + count

        total_score = 0
        total_score += solve_suit(suits['S'])
        total_score += solve_suit(suits['H'])
        total_score += solve_suit(suits['D'])
        total_score += solve_suit(suits['C'])
        
        print(total_score)
    except (IOError, ValueError):
        pass

if __name__ == "__main__":
    main()

算法及复杂度

算法：贪心算法
时间复杂度： $\mathcal{O}(N \log N)$ ，其中 $N$ 是输入的牌种类数。主要开销来自于将所有牌读入并存入 map 中（每次插入为 $\mathcal{O}(\log K)$ ，其中 $K$ 是 map 中的元素数量），以及后续遍历每个花色的牌（每个花色有 $M$ 种牌，遍历一遍为 $\mathcal{O}(M \log M)$ ）。
空间复杂度： $\mathcal{O}(N)$ ，用于存储所有牌的信息。