洛谷P2652题 同花顺问题深度解析 玩转扑克牌算法

一、问题理解

同花顺是指同一花色的连续数字序列。题目要求找出最少需要更换多少张牌，才能使手中所有牌成为同花顺。

二、解题思路

1. 预处理：按花色分组并排序

2. 对每种花色，找出最长的连续数字序列

3. 计算需要更换的牌数 = 总牌数 - 最长序列长度

三、关键算法详解

1. 数据结构设计：

• 使用结构体Card存储每张牌的花色和数字

• 自定义比较函数实现先按花色后按数字排序

2. 滑动窗口技巧：

• 对每种花色维护一个滑动窗口

• 窗口内保持数字连续且差值小于n

• 动态调整窗口大小并记录最大值

四、代码实现

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

struct Card {
    int suit;  // 花色
    int num;   // 数字
};

// 比较函数：先按花色排序，同花色按数字排序
bool cmp(const Card& a, const Card& b) {
    if(a.suit != b.suit) return a.suit < b.suit;
    return a.num < b.num;
}

int main() {
    int n;
    cin >> n;
    vector<Card> cards(n);
    
    for(int i = 0; i < n; i++) {
        cin >> cards[i].suit >> cards[i].num;
    }
    
    // 按花色和数字排序
    sort(cards.begin(), cards.end(), cmp);
    
    int min_changes = n; // 初始化为最大可能值
    
    // 遍历所有可能的同花顺区间
    for(int i = 0; i < n; ) {
        int j = i;
        // 找到相同花色的连续区间
        while(j < n && cards[j].suit == cards[i].suit) j++;
        
        vector<int> nums;
        for(int k = i; k < j; k++) {
            nums.push_back(cards[k].num);
        }
        
        // 去重
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        
        // 滑动窗口找最长连续序列
        int left = 0;
        for(int right = 0; right < nums.size(); right++) {
            while(nums[right] - nums[left] >= n) left++;
            min_changes = min(min_changes, n - (right - left + 1));
        }
        
        i = j;
    }
    
    cout << min_changes << endl;
    return 0;
}

五、边界情况处理

1. 所有牌花色相同的情况

2. 数字完全相同的情况

3. 牌数较少时的特殊情况

六、复杂度分析

时间复杂度：O(nlogn) 主要来自排序操作

空间复杂度：O(n) 存储牌的信息

七、优化方向

1. 使用哈希表加速分组

2. 并行处理不同花色

3. 预处理数字范围

这个实现通过巧妙的排序和滑动窗口技术，高效地解决了同花顺问题，是处理序列类问题的经典范例。