网站预订模板怎么做,赣州app开发,免费的简历模板,获取网站访客qq号小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案#xff0c;分别将它们列为两个数组 {a1, a2, …, an} 和 {b1, b2, …, bm}。两个数组的和相同。
定义一次合并操作可以将某数组内相邻的两个数合并为一个新数#xff0c;新数的值是原来两…小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案分别将它们列为两个数组 {a1, a2, …, an} 和 {b1, b2, …, bm}。两个数组的和相同。
定义一次合并操作可以将某数组内相邻的两个数合并为一个新数新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样即 nm 且对于任意下标 i 满足 aibi。请计算至少需要多少次合并操作可以完成小明的目标。
输入格式
输入共 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^50 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;
}题解二:
前缀和二分法
先对两个序列都求一次前缀和当前缀和相同的时候跳过, 不同的时候分为两种情况:ab的时候, 用二分查找一下第一个等于b的值得下标, 然后加上操作次数; ba的时候, 用二分查找一下第一个等于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;
}觉得写的不错的话, 点个赞吧~
