题目描述
让两个数组合并为一模一样的，求最小合并次数。
思路
把 a，b 数组看为 x，y 两个队列，用 ans 记录合并了几次，合并时会出现 $3$ 种情况。
1. x 的队首等于 y 的队首，尽然相等，直接删除 x 和 y 的队首。
2. x 的队首大于 y 的队首，那么把 y 的前两项合并，然后删除，再加入合并的数字。
3. x 的队首小于 y 的队首，那么把 x 的前两项合并，然后删除，再加入合并的数字。
代码实现
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,a,ans; deque<ll> x,y; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){//在 x 队列中加入加入元素 cin>>a; x.push_back(a); } for(int i=1;i<=m;i++){//在 y 队列中加入加入元素 cin>>a; y.push_back(a); } while(!x.empty()&&!y.empty()){//只要还有 if(x.front()==y.front()){//第一种情况，相等 x.pop_front();//弹出 x 队列中的第一个元素 y.pop_front();//弹出 y 队列中的第一个元素 } if(x.front()>y.front()){//第二种情况，y 队列的第一个元素> x 队列的第一个元素，合并 y 队列的前两个元素 ll y1=y.front();//取出头元素 y.pop_front();//删除 y 队列中的第一个元素 ll y2=y.front();//取出头元素 y.pop_front();//删除 y 队列中的第一个元素 y.push_front(y1+y2);//在放入 y 队列合并的数 ans++;//答案+1 } if(x.front()<y.front()){//第三种情况，x 队列的第一个元素> y 队列的第一个元素，合并 x 队列的前两个元素 ll x1=x.front();//取出头元素 x.pop_front();//删除 x 队列中的第一个元素 ll x2=x.front();//取出头元素 x.pop_front();//删除 x 队列中的第一个元素 x.push_front(x1+x2);/在放入 x 队列合并的数 ans++;//答案+1 } } cout<<ans; return 0; }