2026/7/13 1:34:29
网站建设
项目流程
基本信息
| 项目 | 内容 |
|---|
| 题目编号、来源 | 蓝桥杯决赛D题 数组合并相同 / 第十四届蓝桥杯C++B组 |
| 训练层级 | B 双指针贪心模拟 |
| 知识版块 | 贪心、队列、前缀和分段匹配 |
解题前・关键信号识别
| 维度 | 分析 |
|---|
| 目标、约束、底层结构 | 目标：通过相邻合并操作，让两个数组完全相同，求最少合并次数；约束：只能合并相邻两个数字，合并后数值为两数之和，两数组总和相等；底层结构：双队列分段匹配，哪边队首和小就合并下一段，直到两端相等再同时弹出。 |
| 数据规模 | n,m ≤ 1e5，必须O(n+m)线性算法；暴力模拟/前缀和二分会超时，双队列单次遍历最优。 |
| 候选算法和依据 | 双队列贪心分段；依据：两段前缀和不相等时，只能合并后方相邻元素，每合并一次计数+1，两端相等说明分段匹配完成，同时弹出队首。 |
| 复杂度预判 | O(n+m)，每个元素仅入队、出队一次；空间复杂度O(n+m)存储两个队列。 |
解题后・外化复盘（从会一次到稳定会）
| 维度 | 内容 |
|---|
| 实现结构 / 核心思路 | 第一步分别将两个数组存入队列；第二步循环对比两个队首：若左队首更小，合并左队列下一个元素，合并次数+1；若右队首更小，合并右队列下一个元素，合并次数+1；若相等则同时弹出两个队首；第三步队列为空时输出总合并次数。
因为只能进行加操作，而且和是一样的，所以只要小的数不断往后加直至相等就可以 |
| 错因回溯（逻辑 BUG / 代码实现 BUG） | 代码BUG：队列为空时还访问front()，数组越界；忘记加速cin大数据超时。 |
| 边界和易错点 | 1. 保证两数组总和相等（题目保证，无需额外判断）；2. 每次只能合并当前队列相邻后一位，不能跨多段；3. 1e5大数据建议加ios::sync_with_stdio加速输入；4. 相等时同时弹出，代表一段匹配完成，不增加合并次数。 |
| 下次看到什么信号，我应该想到这个方法 | 看到「两个数组总和相等、相邻合并、使分段完全一致、求最少合并次数」，直接用双队列贪心分段匹配。 |
AC 完整代码
#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;intn,m;queue<longlong>v1,v2;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intans=0;cin>>n>>m;for(inti=0;i<n;i++){longlonga;cin>>a;v1.push(a);}for(inti=0;i<m;i++){longlonga;cin>>a;v2.push(a);}while(!v1.empty()&&!v2.empty()){if(v1.front()>v2.front()){longlonga=v2.front();v2.pop();v2.front()+=a;ans++;}elseif(v1.front()<v2.front()){longlonga=v1.front();v1.pop();v1.front()+=a;ans++;}elseif(v1.front()==v2.front()){v1.pop();v2.pop();}}cout<<ans;return0;}