P9422题解

wmrqwq · 2023-06-24 16:30:22 · 题解

原题链接

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

题目简述

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

解题思路

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

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

参考代码

#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; //输出需要合并的次数
}