問題描述

小明發現有很多方案可以把一個很大的正整數拆成若干正整數的和。他采取了其中兩種方案，分別將他們列為兩個數組?{a1,a2,...,an} 和?{b1,b2,...,bm}。兩個數組的和相同。

定義一次合并操作可以將某數組內相鄰的兩個數合并為一個新數，新數的值是原來兩個數的和。小明想通過若干次合并操作將兩個數組變成一模一樣，即?n=m 且對于任意下標?i?滿足?ai=bi?。請計算至少需要多少次合并操作可以完成小明的目標。

輸入格式

輸入共?3?行。

第一行為兩個正整數?n,?m。

第二行為?n?個由空格隔開的整數?a1,a2,...,an?。

第三行為?m?個由空格隔開的整數 b1?,b2?,...,bm?。

輸出格式

輸出共?1?行，一個整數。

樣例輸入

4 3
1 2 3 4
1 5 4

樣例輸出

1

樣例說明

只需要將?a2 和?a3??合并，數組?a?變為?{1,5,4}，即和?b?相同。

評測用例規模與約定

對于?20% 的數據，保證?n,?m≤。

對于?100% 的數據，保證?n,?m≤，0<ai?,?bi≤。

?

合并規則：按照從左至右的順序依次比較兩個數組中的對應元素，優先選取較小元素與其右邊的元素進行合并。

#include<iostream>
using namespace std;const int N = 1e5+10;
int n, m;
int a[N], b[N];int ans;int main()
{cin>>n>>m;for(int i=1; i<=n; ++i) cin>>a[i];for(int i=1; i<=m; ++i) cin>>b[i];//i 和 j 同步遞增，使用while循環 int i=1, j=1;while(i<=n && j<=m){if(a[i]<b[j]){a[i+1] += a[i];  //合并到下一個元素i++;ans++;}else if(b[j]<a[i]){b[j+1] += b[j];j++;ans++;}else{i++;j++;}}cout<<ans;return 0;
}