[蓝桥杯]-最大的通过数-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/…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...

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

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...