当前位置:首页 > 洛谷 > 洛谷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题解

原创内容 转载请注明出处

分享给朋友:

相关文章

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

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

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

GESP2023年六级真题解析:动态规划解决小杨买饮料问题(洛谷3873)

GESP2023年六级真题解析:动态规划解决小杨买饮料问题(洛谷3873)

一、题目解读小杨买饮料是GESP 2023年六级认证考试中的一道经典动态规划题目,考察学生对背包问题的理解和应用能力。题目描述小杨需要购买n种饮料,每种饮料有特定的体积w和价格v,他要在不超过容量l的...

手搓顺序表类代码注释与详解:从零实现动态数组(新手教程)

一、简介和特点顺序表(Sequential List)是数据结构中基础的一种线性表,其特点是将数据元素存储在连续的内存空间中。通过数组实现,支持随机访问(即通过索引直接访问元素),适用于频繁随机读取的...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

发表评论

访客

看不清,换一张

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