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

[蓝桥杯]-最大的通过数-CPP-二分查找、前缀和

目录

一、题目描述:

二、整体思路:

三、代码:


一、题目描述:

二、整体思路:

  1. 首先要知道不是他们同时选择序号一样的关卡通关,而是两人同时进行两个入口闯关。就是说两条通道存在相同关卡编号的的关卡被通关。
  2. 由于两人必须按各自通道顺序通关,每通关一次要消耗被通关关卡的水晶数,那么很自然想到用前缀和数组来保存各自的消耗的水晶数。
  3. 由于通关关卡数和水晶总数成反比,因此可以枚举所有可能的通关数,通过二分提高查找效率,每次枚举一个可能的通关数都要用一个check函数进行验证。
  4. check函数中,输入可能的通关数,输出完成这个通关数所需要的最小的水晶数,那么一个人的通关数x取值范围是0-mid,另一个人的通关数即为mid-x。利用前缀和数组把两个人所消耗的水晶数相加,每次相加都要和上一次结果比较取最小值。
  5. 注意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-二分查找、前缀和

目录 一、题目描述&#xff1a; 二、整体思路&#xff1a; 三、代码&#xff1a; 一、题目描述&#xff1a; 二、整体思路&#xff1a; 首先要知道不是他们同时选择序号一样的关卡通关&#xff0c;而是两人同时进行两个入口闯关。就是说两条通道存在相同关卡编号的的关卡被通…...

安卓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&#xff1a; 中央处理器&#xff08;Central Processing Unit&#xff09;是一块超大规模的集成电路&#xff0c;是一台计算机的运算核心&#xff08;Core&#xff09;和控制核心&#xff08; Control Unit&#xff09;。 它的功能主要是解释计算机指令以及处理计算机软件…...

鸿蒙车载原生开发,拓展新版图

一天内连发“五弹”、HiCar 4.0首次上车 华为鸿蒙狂扩“汽车朋友圈”-上游新闻 汇聚向上的力量 3月15日&#xff0c;在“华为云&华为终端云服务创新峰会2024”上&#xff0c;华为首批汽车行业伙伴广汽传祺、岚图汽车、零跑汽车、凯翼汽车加入鸿蒙生态合作&#xff0c;华为…...

15届蓝桥杯第二期模拟赛题单详细解析

文章目录 &#x1f9e1;&#x1f9e1;t1_求余&#x1f9e1;&#x1f9e1;思路代码 &#x1f9e1;&#x1f9e1;t2_灌水&#x1f9e1;&#x1f9e1;思路代码 &#x1f9e1;&#x1f9e1;t3_字符显示&#x1f9e1;&#x1f9e1;思路代码 &#x1f9e1;&#x1f9e1;t4_区间最大和…...

mysql统计数据库大小

ps:亲测可行,时间2024-03-15 15:18 mysql统计数据库大小 要统计MySQL数据库的大小&#xff0c;你可以使用以下SQL查询&#xff1a; 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是什么&#xff1f;启动firewalld服务查看默认区域关闭端口访问添加富规则firewall-cmd的区域概念firewall-cmd的常用选项通用选项&#xff1a;状态选项&#xff1a;永久选项&#xff1a;区域选项&#xff1a; firewall-cmd是什么&#xff1f; firewall-…...

创维汽车与创维光伏储能亮相2024上海AWE,感受制造业的升级变迁

2024年3月14日&#xff0c;中国家电及电子消费博览会在上海正式召开。相比往届展会&#xff0c;2024上海AWE进驻更多行业头部力量&#xff0c;出展更多尖端科技&#xff0c;蕴含更深行业思考。创维光伏储能及乘载更先进智驾科技的创维汽车亮相此次展会。 消费电子的革新不断影响…...

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_内存泄漏和内存溢出

本人今年参加了很多面试&#xff0c;也有幸拿到了一些大厂的offer&#xff0c;整理了众多面试资料&#xff0c;后续还会分享众多面试资料。 整理成了面试系列&#xff0c;由于时间有限&#xff0c;每天整理一点&#xff0c;后续会陆续分享出来&#xff0c;感兴趣的朋友可关注收…...

MySQL-HMA 高可用故障切换

本章内容&#xff1a; 了解MySQL MHA搭建MySQL MHAMySQL MHA故障切换 1.案例分析 1.1.1案例概述 目前 MySQL 已经成为市场上主流数据库之一&#xff0c;考虑到业务的重要性&#xff0c;MySQL 数据库 单点问题已成为企业网站架构中最大的隐患。随着技术的发展&#xff0c;MHA…...

深度学习 精选笔记(11)深度学习计算相关:GPU、参数、读写、块

学习参考&#xff1a; 动手学深度学习2.0Deep-Learning-with-TensorFlow-bookpytorchlightning ①如有冒犯、请联系侵删。 ②已写完的笔记文章会不定时一直修订修改(删、改、增)&#xff0c;以达到集多方教程的精华于一文的目的。 ③非常推荐上面&#xff08;学习参考&#x…...

深度学习 Day27——J7对于ResNeXt-50算法的思考

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制&#x1f680; 文章来源&#xff1a;K同学的学习圈子 文章目录 前言问题分析 前言 关键问题&#xff1a;ResNeXt-50中conv_shortcutFalse时…...

华为配置敏捷分布式SFN漫游实验

配置敏捷分布式SFN漫游示例 组网图形 图1 配置敏捷分布式SFN漫游示例组网图 组网需求数据规划配置思路配置注意事项操作步骤配置文件 组网需求 某医院通过部署敏捷分布式网络给医护人员提供WLAN接入服务&#xff0c;以满足医护人员办公的最基本需求。管理员希望终端在覆盖区域内…...

续上篇 qiankun 微前端配置

上篇文章地址&#xff1a;微前端框架 qiankun 配置使用【基于 vue/react脚手架创建项目 】-CSDN博客 主应用&#xff1a; src/main.js 配置&#xff1a; import Vue from vue import App from ./App.vue import router from ./router import { registerMicroApps, start } …...

AI日报:欧盟人工智能法案通过后行业面临合规障碍

文章目录 人工智能新规对web爬网的影响对英国的影响。 人工智能新规 立法者已经通过了欧盟人工智能法案。企业现在必须确保其人工智能应用程序符合规则。 全面的新规定对可能影响公民权利的人工智能系统实施制裁&#xff0c;并有可能彻底禁止某些系统。 违反规定的公司可能面…...

音视频如何快速转二维码?在线生成音视频活码的教程

音频文件的二维码制作步骤是什么样的呢&#xff1f;扫描二维码来展现内容是很流行的一种方式&#xff0c;基本上日常生活中经常会用的图片、音频、视频等都可以使用生成二维码的方式。现在很多的幼儿园或者学校会录制孩子的音频或者视频内容用来展示&#xff0c;那么二维码制作…...

开源堡垒机Jumpserver安装教程

前言:堡垒机的应用场景 公司内有若干台服务器,既有windows的也有linux的, 提供有ERP,OA,Web,报表等等各种服务,往往需要远程登录到服务器上去做运维,但如果给root或者administrator权限,很容易出现不知道谁操作了的问题.如果不同人设置不同账号,又账号过多,权限不足等等其他问题…...

CentOS 7 socat命令端口转发 —— 筑梦之路

命令简介 socat是一个功能强大的命令行工具&#xff0c;也可以看作是netcat的加强版&#xff0c;它可以在两个端口之间建立虚拟通道&#xff0c;实现数据的传输。适用于网络调试、端口转发、安全测试等多种场景&#xff0c;是一个适合网络管理员和开发者的工具 yum在线安装 yu…...

SeaTunnel 2.3.4 Cluster in K8S

参考&#xff1a;seatunnel k8s运行zeta引擎&#xff08;cluster-mode模式&#xff09;_apache seatunnel zeta 启动-CSDN博客 以上参考使用的是2.3.3版本 下载2.3.4版本, 上dlcdn.apache.org下载 &#xff0c;官网下载有问题 wget https://dlcdn.apache.org/seatunnel/2.3.4/…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

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

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

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...