[蓝桥杯]-最大的通过数-CPP-二分查找、前缀和
目录
一、题目描述:
二、整体思路:
三、代码:
一、题目描述:


二、整体思路:
- 首先要知道不是他们同时选择序号一样的关卡通关,而是两人同时进行两个入口闯关。就是说两条通道存在相同关卡编号的的关卡被通关。
- 由于两人必须按各自通道顺序通关,每通关一次要消耗被通关关卡的水晶数,那么很自然想到用前缀和数组来保存各自的消耗的水晶数。
- 由于通关关卡数和水晶总数成反比,因此可以枚举所有可能的通关数,通过二分提高查找效率,每次枚举一个可能的通关数都要用一个check函数进行验证。
- check函数中,输入可能的通关数,输出完成这个通关数所需要的最小的水晶数,那么一个人的通关数x取值范围是0-mid,另一个人的通关数即为mid-x。利用前缀和数组把两个人所消耗的水晶数相加,每次相加都要和上一次结果比较取最小值。
- 注意long long、二分边界问题。
三、代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=2e5+10;
using ll = long long;
ll k;
int arr_l[N];
int arr_r[N];
ll prevfix_l[N];
ll prevfix_r[N];
ll check(ll mid){//返回要通过mid道关卡一共要多少块紫水晶ll ans=INT_MAX;for(int x=0;x<=mid;x++){if(x<=n && mid-x<=m) ans=min(ans,prevfix_l[x]+prevfix_r[mid-x]);}return ans;
}
int main(){cin>>n>>m>>k;for(int i = 1;i<=n;i++){cin>>arr_l[i];prevfix_l[i]=prevfix_l[i-1]+arr_l[i];}for(int i=1;i<=m;i++){cin>>arr_r[i];prevfix_r[i]=prevfix_r[i-1]+arr_r[i];}ll l=0,r=n+m+10;while(l+1!=r){ll mid=(l+r)>>1;//mid是通过的关卡数量if(check(mid)<=k){l=mid;}else{r=mid;}}cout<<l;return 0;
}
相关文章:
[蓝桥杯]-最大的通过数-CPP-二分查找、前缀和
目录 一、题目描述: 二、整体思路: 三、代码: 一、题目描述: 二、整体思路: 首先要知道不是他们同时选择序号一样的关卡通关,而是两人同时进行两个入口闯关。就是说两条通道存在相同关卡编号的的关卡被通…...
安卓UI面试题 26-30
26. Window和DecorView是什么?DecorView又是如何和Window建立联系的?Window是 WindowManager 最顶层的视图,它负责背景(窗口背景)、Title之类的标准的UI元素, Window是一个抽 象类,整个Android系统中, PhoneWindow是 Window的唯一实现类。 至于 DecorView,它是一个顶级 …...
CPU、GPU、IPU、NPU、TPU、LPU、MCU、MPU、SOC、DSP、FPGA、ASIC、GPP、ECU、
CPU: 中央处理器(Central Processing Unit)是一块超大规模的集成电路,是一台计算机的运算核心(Core)和控制核心( Control Unit)。 它的功能主要是解释计算机指令以及处理计算机软件…...
鸿蒙车载原生开发,拓展新版图
一天内连发“五弹”、HiCar 4.0首次上车 华为鸿蒙狂扩“汽车朋友圈”-上游新闻 汇聚向上的力量 3月15日,在“华为云&华为终端云服务创新峰会2024”上,华为首批汽车行业伙伴广汽传祺、岚图汽车、零跑汽车、凯翼汽车加入鸿蒙生态合作,华为…...
15届蓝桥杯第二期模拟赛题单详细解析
文章目录 🧡🧡t1_求余🧡🧡思路代码 🧡🧡t2_灌水🧡🧡思路代码 🧡🧡t3_字符显示🧡🧡思路代码 🧡🧡t4_区间最大和…...
mysql统计数据库大小
ps:亲测可行,时间2024-03-15 15:18 mysql统计数据库大小 要统计MySQL数据库的大小,你可以使用以下SQL查询: SELECT table_schema AS "Database",ROUND(SUM(data_length index_length) / 1024 / 1024, 2) AS "Size (MB)"FROM info…...
centos防火墙firewall-cmd限定特定的ip访问
文章目录 firewall-cmd是什么?启动firewalld服务查看默认区域关闭端口访问添加富规则firewall-cmd的区域概念firewall-cmd的常用选项通用选项:状态选项:永久选项:区域选项: firewall-cmd是什么? firewall-…...
创维汽车与创维光伏储能亮相2024上海AWE,感受制造业的升级变迁
2024年3月14日,中国家电及电子消费博览会在上海正式召开。相比往届展会,2024上海AWE进驻更多行业头部力量,出展更多尖端科技,蕴含更深行业思考。创维光伏储能及乘载更先进智驾科技的创维汽车亮相此次展会。 消费电子的革新不断影响…...
Kafka配置SASL_PLAINTEXT权限。常用操作命令,创建用户,topic授权
查看已经创建的topic ./bin/kafka-topics.sh --bootstrap-server localhost:9092 --list 创建topic 创建分区和副本数为1的topic ./bin/kafka-topics.sh --create --bootstrap-server localhost:9092 --topic acltest --partitions 1 --replication-factor 1 创建kafka用户 …...
[Java、Android面试]_05_内存泄漏和内存溢出
本人今年参加了很多面试,也有幸拿到了一些大厂的offer,整理了众多面试资料,后续还会分享众多面试资料。 整理成了面试系列,由于时间有限,每天整理一点,后续会陆续分享出来,感兴趣的朋友可关注收…...
MySQL-HMA 高可用故障切换
本章内容: 了解MySQL MHA搭建MySQL MHAMySQL MHA故障切换 1.案例分析 1.1.1案例概述 目前 MySQL 已经成为市场上主流数据库之一,考虑到业务的重要性,MySQL 数据库 单点问题已成为企业网站架构中最大的隐患。随着技术的发展,MHA…...
深度学习 精选笔记(11)深度学习计算相关:GPU、参数、读写、块
学习参考: 动手学深度学习2.0Deep-Learning-with-TensorFlow-bookpytorchlightning ①如有冒犯、请联系侵删。 ②已写完的笔记文章会不定时一直修订修改(删、改、增),以达到集多方教程的精华于一文的目的。 ③非常推荐上面(学习参考&#x…...
深度学习 Day27——J7对于ResNeXt-50算法的思考
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 | 接辅导、项目定制🚀 文章来源:K同学的学习圈子 文章目录 前言问题分析 前言 关键问题:ResNeXt-50中conv_shortcutFalse时…...
华为配置敏捷分布式SFN漫游实验
配置敏捷分布式SFN漫游示例 组网图形 图1 配置敏捷分布式SFN漫游示例组网图 组网需求数据规划配置思路配置注意事项操作步骤配置文件 组网需求 某医院通过部署敏捷分布式网络给医护人员提供WLAN接入服务,以满足医护人员办公的最基本需求。管理员希望终端在覆盖区域内…...
续上篇 qiankun 微前端配置
上篇文章地址:微前端框架 qiankun 配置使用【基于 vue/react脚手架创建项目 】-CSDN博客 主应用: src/main.js 配置: import Vue from vue import App from ./App.vue import router from ./router import { registerMicroApps, start } …...
AI日报:欧盟人工智能法案通过后行业面临合规障碍
文章目录 人工智能新规对web爬网的影响对英国的影响。 人工智能新规 立法者已经通过了欧盟人工智能法案。企业现在必须确保其人工智能应用程序符合规则。 全面的新规定对可能影响公民权利的人工智能系统实施制裁,并有可能彻底禁止某些系统。 违反规定的公司可能面…...
音视频如何快速转二维码?在线生成音视频活码的教程
音频文件的二维码制作步骤是什么样的呢?扫描二维码来展现内容是很流行的一种方式,基本上日常生活中经常会用的图片、音频、视频等都可以使用生成二维码的方式。现在很多的幼儿园或者学校会录制孩子的音频或者视频内容用来展示,那么二维码制作…...
开源堡垒机Jumpserver安装教程
前言:堡垒机的应用场景 公司内有若干台服务器,既有windows的也有linux的, 提供有ERP,OA,Web,报表等等各种服务,往往需要远程登录到服务器上去做运维,但如果给root或者administrator权限,很容易出现不知道谁操作了的问题.如果不同人设置不同账号,又账号过多,权限不足等等其他问题…...
CentOS 7 socat命令端口转发 —— 筑梦之路
命令简介 socat是一个功能强大的命令行工具,也可以看作是netcat的加强版,它可以在两个端口之间建立虚拟通道,实现数据的传输。适用于网络调试、端口转发、安全测试等多种场景,是一个适合网络管理员和开发者的工具 yum在线安装 yu…...
SeaTunnel 2.3.4 Cluster in K8S
参考:seatunnel k8s运行zeta引擎(cluster-mode模式)_apache seatunnel zeta 启动-CSDN博客 以上参考使用的是2.3.3版本 下载2.3.4版本, 上dlcdn.apache.org下载 ,官网下载有问题 wget https://dlcdn.apache.org/seatunnel/2.3.4/…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
