洛谷2652题解析：同花顺排序问题的动态规划与滑动窗口优化

一、题目解读

洛谷2652题要求对一组扑克牌进行排序，目标是找到最少需要调整的次数，使得所有牌形成同花顺。题目中，扑克牌由花色和数字组成，需先按花色排序，再在同花色内按数字排序。核心难点在于如何处理花色与数字的组合排序，以及如何高效寻找最优调整次数。

二、解题思路

采用以下思路：

1. 定义Card结构体存储花色和数字；

2. 自定义比较函数，优先按花色排序，同花色按数字排序；

3. 遍历排序后的牌组，找到相同花色的连续区间；

4. 对区间内数字去重，利用滑动窗口找到最长连续子序列；

5. 通过子序列长度计算调整次数，动态更新最小值。

三、解题步骤

1. 输入牌组数量n，读取每张牌的花色和数字；

2. 调用sort函数，基于自定义比较函数进行排序；

3. 遍历牌组，使用双指针定位同花色区间；

4. 对区间内数字去重，并存储到临时数组；

5. 通过滑动窗口（左右指针）计算最长连续子序列长度；

6. 更新最小调整次数min_changes = min(min_changes, n - 子序列长度)；

7. 输出最终结果。

四、代码与注释

#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;
}

五、总结

本解法结合排序、去重与滑动窗口技术，通过动态规划思想高效求解。核心在于将问题拆解为同花色区间的连续子序列查找，利用滑动窗口降低时间复杂度。算法时间复杂度为O(nlogn)，空间复杂度为O(n)。实际应用中，可进一步优化窗口移动逻辑或采用更高效的数据结构。

参考：牛客2652题解