当前位置:首页 > 洛谷 > 洛谷2652题解析:同花顺排序问题的动态规划与滑动窗口优化

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

3天前

洛谷2652题解析:同花顺排序问题的动态规划与滑动窗口优化 洛谷题解 同花顺算法 动态规划 滑动窗口 扑克牌排序 C++ 第1张

一、题目解读

洛谷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题解

原创内容 转载请注明出处

分享给朋友:

相关文章

力扣912排序题终极解法:递归分割 + 双指针合并详解

力扣912排序题终极解法:递归分割 + 双指针合并详解

题目解读给定一个整数数组,要求将其按升序排列并返回。题目通常隐含对算法时间复杂度的要求,理想情况下需实现 O(n log n) 的时间复杂度。本题看似简单,但需要选择合适的排序算法(如归并排序、快速排...

力扣第92题:三步定位 精准反转链表指定区间

力扣第92题:三步定位 精准反转链表指定区间

题目解读给定一个单链表和两个整数left与right,要求将链表中从第left个节点到第right个节点的部分进行反转,而保持其他部分不变。例如,对于链表1→2→3→4→5,left=2,right=...

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

力扣965题深度解析:单值二叉树的判断技巧

力扣965题深度解析:单值二叉树的判断技巧

重新解读题目 判断一棵二叉树是否为“单值二叉树”,即所有节点的值是否完全相同。题目看似简单,实则考验对树结构递归特性的理解。若一棵树的所有节点值相同,其必然满足:根节点与左右子树的值一致,且...

力扣540题:线性扫描法如何高效定位唯一数

力扣540题:线性扫描法如何高效定位唯一数

题目重解一个严格递增的有序数组中,除某个元素外,其余每个元素均出现两次。这个看似简单的条件背后隐藏着巧妙的规律——单一元素会打破数组的"成对对称性"。题目要求以O(log n)时间...

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。