考察双指针+贪心
利用两个指针,调节左右指针到达一个平衡位置然后合并成一个数
合成所需要的次数是len1+len2-2(两个数合成为一个数只需要1步)
代码如下
#include<iostream>
#define int long long
using namespace std;
const int N=100010;
signed main()
{
int n,m;
int a[N],b[N];
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=m;j++) cin>>b[j];
int ans=0;
int l=0,r=0;
while(l<n)
{
if(a[l]==b[r])//如果在这两个数本来就相等不需要合并,指针都往后移
{
l++,r++;
}
else
//如果需要合并就要让两个指针达到一个平衡位置,也就是求和相等才能合并成两个相等的数
{
int sum1=a[l],sum2=b[r];
int len1=1,len2=1;
while(sum1!=sum2)
{
if(sum1<sum2)
{
sum1+=a[++l];
len1++;
}
else if(sum1>sum2)
{
sum2+=b[++r];
len2++;
}
}
l++,r++;
ans+=len1+len2-2;
}
}
cout<<ans<<endl;
return 0;
}