洛谷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题解
原创内容 转载请注明出处