小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将它们列为两个数组 {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 的开头包含三种情况:

1. a[0]等于b[0], 此时把两个开头都删除掉
2. b[0] < a[0], 此时把b[0]和b[1]相加, 然后删除b[0]和b[1], 把b[0]和b[1]相加的结果放到b的开头, 相当于是合并b的前两个数, cnt ++ (cnt是总操作数)
3. a[0] < b[0], 此时把a[0]和a[1]相加, 然后删除a[0]和a[1], 把a[0]和a[1]相加的结果放到a的开头, 相当于是合并a的前两个数, cnt ++

ac代码👇

#include 
using namespace std;
#define int long long    // 序列中的数最大是1e5, 如果两个都是1e5, 那么这两个数相加会爆int
const int N = 1e5 + 10;
int a[N], b[N];
signed main()
{
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int j = 0; j < m; j ++) cin >> b[j];
	
	int i = 0, j = 0, cnt = 0;
	while (i < n && j < m)  // 也可以用dequeue, 但运行效率会低一些
	{
		if (a[i] == b[j]) i ++, j ++;    
		else if (a[i] < b[j]) a[i + 1] = a[i] + a[i + 1], i ++, cnt ++;
		else if (b[j] < a[i]) b[j + 1] = b[j] + b[j + 1], j ++, cnt ++;
	}
	cout << cnt << endl;
	return 0;
}

---

题解二:

前缀和+二分法

• 先对两个序列都求一次前缀和
• 当前缀和相同的时候跳过, 不同的时候分为两种情况:
• a

  #include 
  using namespace std;
  #define int long long
  const int N = 1e5 + 10;  // 会爆int
  int a[N], b[N];
  signed main()
  {
  	int n, m; cin >> n >> m;
  	for (int i = 1; i <= n; i ++) 
  	{
  		cin >> a[i];
  		a[i] += a[i - 1];    // 求前缀和
  	}
  	for (int j = 1; j <= m; j ++) 
  	{
  		cin >> b[j];
  		b[j] += b[j - 1];  // 求前缀和
  	}
  	
  	int i = 1, j = 1, cnt = 0;
  	while (i <= n && j <= m) 
  	{
  		if (a[i] == b[j]) i ++, j ++;
  		
  		else if (a[i] < b[j])
  		{
  			int l = i, r = n;
  			while (l < r)
  			{
  				int mid = l + r >> 1;
  				if (a[mid] >= b[j]) r = mid;	// 找到的是第一个满足 条件的下标 
  				else l = mid + 1;
  			}
  			cnt += l - i;
  			i = l;
  			
  		}
  		
  		else if (b[j] < a[i])
  		{
  			int l = j, r = m;
  			while (l < r)
  			{
  				int mid = l + r >> 1;
  				if (b[mid] >= a[i]) r = mid;  // 找到的是第一个满足 条件的下标
  				else l = mid + 1;
  			}
  			cnt += l - j;
  			j = l;
  			
  		}
  	}
  	cout << cnt << endl;
  	return 0;
  }
  

  觉得写的不错的话, 点个赞吧~