当前位置: 首页 > 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], …...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...