[蓝桥杯]-最大的通过数-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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/457394.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PlantUML Integration 编写短信服务类图

PlantUML Integration 写一个类图&#xff0c;主要功能为 1、编写一个serviceSms短信服务类&#xff1b; 2、需要用到短信的地方统一调用基建层的服务即可&#xff1b; 3、可以随意切换、增加短信厂商&#xff0c;不需要更改场景代码&#xff0c;只需要更改application.yml 里面…

SQLiteC/C++接口详细介绍之sqlite3类(七)

上一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;六&#xff09; 下一篇&#xff1a; SQLiteC/C接口详细介绍之sqlite3类&#xff08;八&#xff09;&#xff08;未发表&#xff09; 22.sqlite3_create_collation、sqlite3_create_collation16和sqlite3_creat…

JavaEE--小Demo

目录 下载包 配置 修改文件 pom.xml application.properties 创建文件 HelloApi.java GreetingController.java Greeting.java DemoApplication.java 运行包 运行命令 mvn package cd target dir java -jar demo-0.0.1-SNAPSHOT.jar 浏览器测试结果 下载包 …

网络安全专题第一篇:网络安全的来源

目录 一.网络安全的由来。 二.网络安全漏洞在哪里 三.网络安全规范操作 1.从业务入手 2.从安全体系入手 3.从管理入手 四.可能遇到的网络攻击 1.DDOS 2.勒索攻击 3.单包攻击 4.员工删库跑路 5.熊猫烧香 五.应对方法 1.清洗 2.提高服务器的承受能力 3.防火墙 4…

证券公司如何应对大数据调度系统的高负载挑战

​在金融行业&#xff0c;数据处理和任务调度是日常运营的重要组成部分。随着业务量的激增&#xff0c;日益增长的任务量和复杂的资源管理需求&#xff0c;要求该系统不仅要稳如磐石&#xff0c;还需灵活高效。 本文将探讨某证券公司在应对这些挑战时所采用的策略&#xff0c;并…

tomcat的webapp文件中发布web应用

一、Web服务器 1.什么是Web 概述&#xff1a; web(World Wide Web)即全球广域网&#xff0c;也称为万维网&#xff0c;它是一种基于超文本和HTTP的、全球性的、动态交百的、跨平台的分布式图形信息系统。是建立在internet上的一种网络服务&#xff0c;为浏览者在Intern…

笔记80:在 Ubuntu 中安装显卡驱动

一、关于显卡的两个基本概念 -- 显卡驱动 / 显卡BIOS &#xff08;1&#xff09;什么是BIOS BIOS的作用&#xff1a;BIOS是电脑上电开机时加载进内存的第一个程序&#xff0c;CPU会执行他进行系统自检&#xff0c;然后通过其中的指令加载操作系统&#xff1b;例如主板BIOS&am…

react 项目如何暴露 webpack配置文件

首先创建一个项目&#xff1a; // 全局安装 create-react-app 脚手架 npm install create-react-app -g// 创建项目 create-react-app demo 创建完成后&#xff0c;进到项目根目录&#xff0c;执行以下命令&#xff1a; npm run eject 出现以下命令&#xff1a; 选择yes即可…

【Unity】Transform、Rigidbody、CharacterController移动

前言 在使用Unity开发的时候&#xff0c;移动是最最基础的一个需求&#xff0c;我来给大家简单的讲一下Unity中的几种常见的移动方法。 1.Transform移动 Transform移动就是修改物体的position ①修改位置 这里要注意&#xff1a;坐标分为世界坐标和本地坐标 //将物体的世界坐…

import gdal 报错

1.下载gdal https://www.lfd.uci.edu/~gohlke/pythonlibs/#gdal 2.安装正确版本 &#xff08;1&#xff09;查看python版本 python -v我的版本Python 3.7.9 建议下载 GDAL-3.4.2-cp37-cp37m-win_amd64.whl &#xff08;2&#xff09;放到Scripts文件夹下 执行 pip install GD…

Unity Timeline学习笔记(2) - PlayableTrack

PlayableTrack 是可自定义播放的轨道。我们可以通过进入轨道后调用自己的函数方法&#xff0c;使用起来也是比较顺手的。 添加轨道 我们点击加号添加 这样就有一个空轨道了&#xff0c;然后我们创建两个测试脚本。 添加脚本 分别是Playable Behaviour和PlayableAsset脚本。…

吴恩达深度学习笔记:神经网络的编程基础2.9-2.14

目录 第一门课&#xff1a;神经网络和深度学习 (Neural Networks and Deep Learning)第二周&#xff1a;神经网络的编程基础 (Basics of Neural Network programming)2.9 逻辑回归中的梯度下降&#xff08;Logistic Regression Gradient Descent&#xff09; 第一门课&#xff…

vue 基于elementUI/antd-vue, h函数实现message中嵌套链接跳转到指定路由 (h函数点击事件的写法)

效果如图&#xff1a; 点击message 组件中的 工单管理&#xff0c; 跳转到工单管理页面。 以下是基于vue3 antd-vue 代码如下&#xff1a; import { message } from ant-design-vue; import { h, reactive, ref, watch } from vue; import { useRouter } from vue-router; c…

蓝桥杯单片机快速开发笔记——定时器

一、基本原理&#xff1a; 定时器的作用&#xff1a; 定时器是一种用于产生精确时间延时的模块&#xff0c;可以在程序中用来进行时间控制、计时等操作。 定时器的工作原理&#xff1a; 51单片机的定时器是通过内部的计数器来实现的&#xff0c;计数器每隔一个固定的时间周期自…

C#,数值计算,矩阵相乘的斯特拉森(Strassen’s Matrix Multiplication)分治算法与源代码

Volker Strassen 1 矩阵乘法 矩阵乘法是机器学习中最基本的运算之一,对其进行优化是多种优化的关键。通常,将两个大小为N X N的矩阵相乘需要N^3次运算。从那以后,我们在更好、更聪明的矩阵乘法算法方面取得了长足的进步。沃尔克斯特拉森于1969年首次发表了他的算法。这是第…

速卖通安全测评补单技术提升运营安全性

对于一个新品来说&#xff0c;最大的问题就是评论。没有评论&#xff0c;你的广告就不能打的很靠前&#xff0c;那样你的转化率就会非常低&#xff0c;数据也很差。新品运气不好的来两个一星差评&#xff0c;链接可能就此废掉&#xff0c;做不上去了。所以虽然平台管的非常的严…

从根到叶:深度理解哈希表

​​​​​​​ 一.哈希表的概念 关于查找元素时&#xff1a; 在顺序结构以及平衡树 中&#xff0c;元素关键码与其存储位置之间没有对应的关系&#xff0c;因此在 查找一个元素时&#xff0c;必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N) &#xff0c;平衡树中…

MySQL 系统变量查看与设置(System Variables Configuration)

MySQL中有大量的系统变量控制服务器的行为&#xff0c;大部分的系统变量是不需要我们调整的&#xff0c;保持默认即可。但为了获得更高的性能和稳定性&#xff0c;有时需要适当对部分变量进行调整&#xff0c;本文总结了MySQL中系统变量的查看与设置方法。 目录 一、变量的类型…

学点Java打小工——Day2Day3一点作业

1 猜数字&#xff08;10次机会&#xff09; 随机生成[1,1000]的一个数&#xff0c;输入你猜的数程序会给出反馈&#xff0c;直到猜对或次数用尽(10次)。 //猜数字 10次机会Testpublic void guessNumber() {Random random new Random();// [0, 1000) 1// [1, 1000]int num ra…

SQLiteC/C++接口详细介绍之sqlite3类(六)

快速前往文章列表&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;五&#xff09; 下一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;七&#xff09; 19. sqlite3_changes与sqlite3_changes64 是SQLite中用…