当前位置: 首页 > news >正文

蓝桥杯-合并数列

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

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

相关文章:

蓝桥杯-合并数列

小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案&#xff0c;分别将它们列为两个数组 {a1, a2, …, an} 和 {b1, b2, …, bm}。两个数组的和相同。 定义一次合并操作可以将某数组内相邻的两个数合并为一个新数&#xff0c;新数的值是原来两…...

《web应用技术》第9次课后作业

一、将前面的代码继续完善功能 1、采用XML映射文件的形式来映射sql语句&#xff1b; 2、采用动态sql语句的方式&#xff0c;实现条件查询的分页。 二、学习git的使用。 1、每个小组将自己的项目上传到gitee&#xff0c;学会协作开发&#xff1b; 2、学会从gitee上拉取项目…...

FRAUDARCatchSync算法简介

参考&#xff1a;https://blog.51cto.com/u_15127663/2778705 1. 背景 Fraudar 要解决的问题是&#xff1a;找出社交网络中最善于伪装的虚假用户簇。虚假用户会通过增加和正常用户的联系来进行伪装&#xff0c;而这些伪装(边)会形成一个很密集的子网络&#xff0c;可以通过定义…...

刷题之将有序数组转换成二叉搜索树(leetcode)

将有序数组转换成二叉搜索树 正常递归&#xff0c;中序遍历 递归经常会把自己绕晕&#xff0c;还是得画图分析 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(null…...

K-means聚类模型教程(个人总结版)

K-means聚类是一种广泛应用于数据挖掘和数据分析的无监督学习算法。它通过将数据点分成K个簇&#xff08;cluster&#xff09;&#xff0c;使得同一簇内的数据点之间的相似度最大&#xff0c;不同簇之间的相似度最小。本文将详细介绍K-means聚类算法的背景、基本原理、具体实现…...

android怎么告诉系统不要回收

在Android中&#xff0c;如果你想告诉系统不要回收你的应用程序&#xff0c;可以通过设置Activity的属性来实现。你可以设置android:configChanges属性&#xff0c;指定在哪些配置更改时不重新创建Activity。 例如&#xff0c;如果你想指示系统在屏幕方向更改时不要重新创建Ac…...

【FAQ】HarmonyOS SDK 闭源开放能力 —IAP Kit(2)

1.问题描述&#xff1a; 应用内支付IAP Kit和Payment Kit的区别以及适用场景&#xff1f; 解决方案&#xff1a; IAP Kit是四方支付&#xff0c;仅支持在线虚拟商品&#xff0c;如会员&#xff0c;游戏钻石等&#xff0c;双框架支持全球&#xff0c;目前单框架暂时只支持国内…...

ubuntu设置root开机登录,允许root用户ssh远程登录

ubuntu与centos系统不同&#xff0c;默认root开机不能登录。 1、输入一下命令创建root密码&#xff0c;根据提示输入新密码 sudo passwd root 2、打开gdm-autologin文件&#xff0c;将auth required pam_succeed_if.so user ! root quiet_success这行注释掉&#xff0c;这行就…...

Web测试面试题(二)

一&#xff1a;简述HTTP协议的状态码包含哪些&#xff1f; 2XX&#xff0c;表示成功 3XX&#xff0c;表示重定向 4XX&#xff0c;表示客户端错误 5XX&#xff0c;表示服务器错误 二&#xff1a;HTTP和HTTPS的区别&#xff1f; 《1》安全性上的区别&#xff1a; HTTPS&#x…...

VBA宏指令写的方法突然不能用了

背景:项目组有个自动化测试项目,实在excel中利用VBA开发的;时间比较久远,我前面的哥们走后,这个软件一直在用,最近系统不知道是不是更新的缘故;有些代码除了问题; 先上源码: Dim Conn As Object, Rst As Object Dim sqlStr$ Dim str_start_SN$, str2$ str_start_SN …...

第13章 Python建模库介绍

以下内容参考自https://github.com/iamseancheney/python_for_data_analysis_2nd_chinese_version/blob/master/%E7%AC%AC05%E7%AB%A0%20pandas%E5%85%A5%E9%97%A8.md 《利用Python进行数据分析第2版》 用以学习和记录。 本书中&#xff0c;我已经介绍了Python数据分析的编程基…...

IP学习——ospf1

OSPF:开放式最短路径优先协议 无类别IGP协议&#xff1a;链路状态型。基于 LSA收敛&#xff0c;故更新量较大&#xff0c;为在中大型网络正常工作&#xff0c;需要进行结构化的部署---区域划分、ip地址规划 支持等开销负载均衡 组播更新 ---224.0.0.5 224.0.0.6 …...

别说废话!说话说到点上,项目高效沟通的底层逻辑揭秘

假设你下周要在领导和同事面前汇报项目进度&#xff0c;你会怎么做&#xff1f;很多人可能会去网上搜一个项目介绍模板&#xff0c;然后按照模板来填充内容。最后&#xff0c;汇报幻灯片做了 80 页&#xff0c;自己觉得非常充实&#xff0c;但是却被领导痛批了一顿。 这样的境…...

前后端编程语言和运行环境的理解

我已重新检查了我的回答,并确保信息的准确性。以下是常用的编程语言,以及它们通常用于前端或后端开发,以及相应的框架和运行环境: 前端开发 JavaScript 框架:React, Angular, Vue.js, Ember.js, Backbone.js运行环境:Web 浏览器HTML (HyperText Markup Language) 不是编…...

一顿五元钱的午餐

在郑州喧嚣的城市一隅&#xff0c;藏着一段鲜为人知的真实的故事。 故事的主角是一位年过半百的父亲&#xff0c;一位平凡而又伟大的劳动者。岁月在他脸上刻下了深深的痕迹&#xff0c;但他眼神中闪烁着不屈与坚韧。 他今年52岁&#xff0c;为了给远在家乡的孩子们一个更好的…...

【前端每日基础】day60——TDK三大标签及SEO引擎优化

TDK 是指 Title&#xff08;标题&#xff09;、Description&#xff08;描述&#xff09;、Keywords&#xff08;关键词&#xff09;这三个网页的重要元信息标签&#xff0c;对于 SEO&#xff08;搜索引擎优化&#xff09;至关重要。下面是它们的作用和 SEO 优化建议&#xff1…...

vscode添加代办相关插件,提高开发效率

这里写目录标题 前言插件添加添加TODO Highlight安装TODO Highlight在项目中自定义需要高亮显示的关键字 TODO Tree安装TODO Tree插件 单行注释快捷键 前言 在前端开发中&#xff0c;我们经常会遇到一些未完成、有问题或需要修复的部分&#xff0c;但又暂时未完成或未确定如何处…...

JS对象超细

目录 一、对象是什么 1.对象声明语法 2.对象有属性和方法组成 二、对象的使用 1.对象的使用 &#xff08;1&#xff09;查 &#xff08;2&#xff09;改 &#xff08;3&#xff09;增 &#xff08;4&#xff09;删&#xff08;了解&#xff09; &#xff08;5&#xf…...

远程PLC、工控设备异地调试,贝锐蒲公英异地组网方案简单高效

北京宇东宁科技有限公司专门提供非标机电设备&#xff0c;能够用于金属制品的加工制造。设备主要采用西门子的PLC作为控制系统&#xff0c;同时能够连接上位机用于产量、温度、压力、电机运行数据的监控&#xff0c;以及工厂的大屏呈现需求。目前&#xff0c;客户主要是市场上的…...

【算法】梦破碎之地---三数之和

相信大家都有做过两数之和&#xff0c; 题目链接&#xff1a; 15. 三数之和 - 力扣&#xff08;LeetCode&#xff09; 在文章的开始让我们回顾一下三数之和吧&#xff01; 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], …...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...