自动搬运

查看原文

来自洛谷，原作者为

	wmrqwq 会登顶的。

搬运于2025-08-24 22:48:13，当前版本为作者最后更新于2023-06-24 16:30:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

P9422 [蓝桥杯 2023 国 B] 合并数列

题目简述

有两个和都相同的数组，现在要通过最少的合并操作使得两个数组变成一模一样。

解题思路

我们可以把两个数列看做两个队列。定义 $a1$，$a2$ 两个队列用于存储两个数组，再遍历一遍这两个队列，遍历的时候一共有 $3$ 种情况：

1. $a1$ 的第一项小于 $a2$ 的第一项，这时就需要将 $a1$ 队列中的第 $1$ 项和第 $2$ 项合并，弹出 $a2$ 队列中的第一个元素，以及将合并次数增加 $1$ 。

2. $a1$ 的第一项大于 $a2$ 的第一项，这时就需要将 $a2$ 队列中的第 $1$ 项和第 $2$ 项合并，弹出 $a2$ 队列中的第一个元素，以及将合并次数增加 $1$ 。

3. $a1$ 的第一项等于 $a2$ 的第一项，这时就需要弹出 $a1$ 队列中的第一个元素以及弹出 $a2$ 队列中的第一个元素。

最后再输出需要合并的次数即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,a,sum;//sum 用于记录答案 
deque<int>a1,a2;
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>a,a1.push_back(a);//输入 n 次 a，并在 a1 队列中加入 a 元素
	for(int i=0;i<m;i++)
		cin>>a,a2.push_back(a);//输入 m 次 a，并在 a2 队列中加入 a 元素
	while(!a1.empty())//如果 a1 队列还有剩余元素，那么就继续运行程序
	{
		if(a1.front()==a2.front())//如果相等就直接出队 
		{
			a1.pop_front();//弹出 a1 队列中的第一个元素
			a2.pop_front();//弹出 a2 队列中的第一个元素
		}
		else if(a1.front()>a2.front())//如果a2小就合并a2的前两个数
		{
			a2[1]+=a2[0];//将 a2 队列中的第 1 项和第 2 项合并
			a2.pop_front();//弹出 a2 队列中的第一个元素
			sum++;//将合并次数增加 1 
		}
		else//如果 a1 小就合并 a1 前两个数
		{ 
			a1[1]+=a1[0];//将 a1 队列中的第 1 项和第 2 项合并
			a1.pop_front();//弹出 a2 队列中的第一个元素
			sum++;//将合并次数增加 1 
		} 
	}
	cout<<sum<<endl; //输出需要合并的次数
}