【双指针】P9422 [蓝桥杯 2023 国 B] 合并数列
题解：P9422 [蓝桥杯 2023 国 B] 合并数列标题传送门：P9422 [蓝桥杯 2023 国 B] 合并数列
一、标题重述
小明有两个正整数数组 a 和 b，它们的和相同。每次操作可以将数组中相邻的两个数合并为一个新数（新数是这两个数的和）。问最少须要多少次操作才能使两个数组变得完全相同。
二、标题分析
我们须要找到最少的合并操作次数，使得两个数组最终完全相同。关键在于如何匹配两个数组中的元素，使得它们可以通过合并操作达到同等。
三、解题思绪
这道题可以利用双指针贪心算法：
[*]用两个指针分别遍历数组 a 和 b
[*]比较当前两个指针所指的元素和：
[*]假如 a 的和较小，就合并 a 的下一个元素，增长操作次数
[*]假如 b 的和较小，就合并 b 的下一个元素，增长操作次数
[*]假如相等，则同时移动两个指针
[*]重复上述过程直到两个数组都被完全遍历
四、算法讲解
算法原理
贪心算法：每次选择当前最优的决策（即尽可能匹配当前元素，不匹配时才合并）。
利用场景
适用于须要将序列分段匹配的问题，特别是当分段的和须要相等时。
算法实现步骤
[*]初始化两个指针 i=1, j=1
[*]初始化当前和 x=a, y=b
[*]循环直到两个数组都被遍历完：
[*]假如 x == y：移动两个指针，重置当前和
[*]假如 x < y：合并 a 的下一个元素到 x
[*]假如 x > y：合并 b 的下一个元素到 y
[*]每次合并操作增长计数器
例子讲解
以样例为例：
a = , b =
[*]初始 x=1, y=1 → 相等，i=2,j=2
[*]x=2, y=5 → x<y，合并 a2和a3 → x=5，操作+1
[*]x=5, y=5 → 相等，i=4,j=3
[*]x=4, y=4 → 相等，结束
总操作次数为1
五、代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, m;
int a, b;
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a;
for (int i = 1; i <= m; i++)
cin >> b;
int ans = 0;
// 双指针遍历两个数组
for (int i = 1, j = 1; i <= n || j <= m;)
{
int x = a, y = b;
// 当前和不相等时，合并较小的那一方
while (x != y)
{
if (x < y)
{
i++;
x += a;
ans++; // 合并操作计数
}
else
{
j++;
y += b;
ans++; // 合并操作计数
}
}
i++, j++; // 当前和相等，移动指针
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
六、代码重点细节表明
[*]双指针初始化：i和j分别初始化为1，指向数组的第一个元素
[*]当前和比较：x和y分别记载当前a数组和b数组的累加和
[*]合并操作：当x和y不相等时，总是合并较小一方的下一个元素
[*]操作计数：每次合并都增长ans计数器
[*]指针移动：当x和y相等时，同时移动两个指针
七、复杂度分析
[*]时间复杂度：O(n+m)，因为每个元素最多被访问一次
[*]空间复杂度：O(n+m)，用于存储两个数组
八、关键点
[*]贪心计谋的精确性：通过局部最优（当前和匹配）达到全局最优
[*]双指针的高效性：线性时间办理问题
[*]界限处置惩罚：循环条件为i≤n || j≤m，确保全部元素都被处置惩罚
九、总结
本题通过贪心算法和双指针技能，高效地办理了数组合并匹配问题。关键在于理解如何通过局部合并操作达到全局匹配，以及如何精确实现双指针的移动逻辑。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]