小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将它们列为两个数组 {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 ≤ 10^3。
对于 100% 的数据，保证 n, m ≤ 10^5，0 < ai, bi ≤ 10^5。
题解:
这题有两种写法, 第一种:模拟队列, 第二种:前缀和+二分
题解一:
模拟队列法
对于两个序列 a 和 b 的开头包含三种情况:
- a[0]等于b[0], 此时把两个开头都删除掉
- b[0] < a[0], 此时把b[0]和b[1]相加, 然后删除b[0]和b[1], 把b[0]和b[1]相加的结果放到b的开头, 相当于是合并b的前两个数, cnt ++ (cnt是总操作数)
- a[0] < b[0], 此时把a[0]和a[1]相加, 然后删除a[0]和a[1], 把a[0]和a[1]相加的结果放到a的开头, 相当于是合并a的前两个数, cnt ++
ac代码
标签：10,cnt,数列,int,合并,mid,蓝桥,++,前缀 From： https://www.cnblogs.com/xxctx/p/18209335