蓝桥杯-合并数列
小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将它们列为两个数组 {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代码👇
#include <bits/stdc++.h>
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<b的时候, 用二分查找一下"第一个等于b的值得下标", 然后加上操作次数; b<a的时候, 用二分查找一下"第一个等于a的值得下标", 然后加上操作次数
#include <bits/stdc++.h>
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;
}
觉得写的不错的话, 点个赞吧~
热门相关：八零喜事之肥妻大翻身 钓龙 车下的欲望 回到古代当国师 与隔壁夫妇交换高尔夫