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

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

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

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

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...