牛客小白月赛104 —— C.小红打怪

C.小红打怪

1.题目:

2.样例

输入

5
1 2 3 4 5

输出

2

说明
第一回合,小红攻击全体怪物,队友1攻击5号怪物,队友2攻击4号和5号怪物,剩余每只怪物血量为[0,1,2,2,2]。
第二回合,小红攻击全体怪物,队友1攻击5号怪物,队友2攻击3号和4号怪物,即可击杀所有怪物。

3.思路

        其实这题就是心里想的那样的,我当时以为有什么简单的方法,没想到就是暴力过的

我们用二分答案法,从1——数组中的最大值,如果mid满足条件,则用res保存答案,向左边二分,找到最小的回合数;不满足条件,不保存答案,向右边二分。

那么这个条件是什么呢?

        我们在确定了回合数的情况下,怎么判断是否满足条件,我们先使用小红的技能,用数组b记录怪兽剩余的血量,再使用队友二的范围攻击,为了不浪费技能,我们一定要确保相邻的两个怪兽有血量,且是刚好使该怪兽血量变为零,如果没有相邻两个怪兽有血量,那么把剩余的队友二的技能次数跟队友一的技能次数合并相加,就当作单个技能技能攻击使用,然后不断的枚举怪兽的剩余血量,如果还有血量,就清零,把技能使用次数也减少,如果技能使用次数变为负数或者i没有到n+1,这说明这个回合数不满足条件。

具体代码实现:

#include <iostream>
using namespace std;
const int N = 1e5+10;
int n,m,res;
int a[N],b[N];bool check(int x){b[0]=0;int x1=x;for(int i=1;i<=n;i++){b[i]=a[i]-x;if(b[i]>0&&b[i-1]>0){int t=min(b[i],b[i-1]);t=min(x1,t);x1-=t;	//不用弄额外的条件去限制x1//因为x1最后一定是>=0,因为t=min(t,x1) b[i]-=t;b[i-1]-=t;}}int x2=x+x1;int i=1;for(;i<=n;i++){if(b[i]>0){x2-=b[i];b[i]=0;	}if(x2<0)break;}if(i==n+1&&x2>=0){return true;}else{return false;}
} void solve(){int l=1,r=m;while(l<=r){int mid=l+(r-l)/2;if(check(mid)){res=mid;r=mid-1;}else{l=mid+1;}}printf("%d\n",res);
}int main(void){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];m=max(m,a[i]);}solve();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

python画图|text()和dict()初探

【1】引言 在进行hist()函数的学习进程中&#xff0c;了解到了subplot_mosaic()函数&#xff0c;在学习subplot_mosaic()函数的时候&#xff0c;又发现了text()和dict()函数。 经探究&#xff0c;text()和dict()函数有很多一起使用的场景&#xff0c;为此&#xff0c;我们就一…

BUG: scheduling while atomic

▌▌上篇文章的内容还没有结束 中断处理函数中如果执行了调度&#xff0c;会发生什么 ▌这次&#xff0c;我修改了程序&#xff0c;在中断处理函数中调用了msleep 程序执行后&#xff0c;会有这样的日志 ▌关键就是这句 BUG: scheduling while atomic 我们追代码&#xff0c;可…

算法 -选择排序

博客主页&#xff1a;【夜泉_ly】 本文专栏&#xff1a;【算法】 欢迎点赞&#x1f44d;收藏⭐关注❤️ 文章目录 &#x1f4a1;选择排序1. &#x1f504; 选择排序&#x1f5bc;️示意图&#x1f4d6;简介&#x1f4a1;实现思路1&#x1f4bb;代码实现1&#x1f4a1;实现思路2…

ubuntu 22.04 镜像源更换

双11抢了个云服务器&#xff0c;想要整点东西玩玩&#xff0c;没想到刚上来就不太顺利 使用sudo apt update更新软件&#xff0c;然后发生了如下报错 W: Failed to fetch http://mirrors.jdcloudcs.com/ubuntu/dists/jammy/InRelease 理所当然想到可能是镜像源连接不是很好&…

2016年7月29日至2017年2月21日NASA大气层层析(ATom)任务甲醛(HCHO)、羟基(OH)和OH生产率的剖面积分柱密度

目录 简介 摘要 引用 网址推荐 知识星球 机器学习 ATom: Column-Integrated Densities of Hydroxyl and Formaldehyde in Remote Troposphere ATom&#xff1a; 远对流层中羟基和甲醛的柱积分密度 简介 该数据集提供了甲醛&#xff08;HCHO&#xff09;、羟基&#xff…

一夜吸粉10万!AI妖精变身视频如何做的?5分钟你也能赶上末班车!

本文背景 最近有小伙伴跟我发了一个AI视频&#xff0c;问我是怎么做的&#xff1f; 很多人在各大自媒体平台&#xff0c;像某音、蝴蝶号都刷到过下面这种妖精变身的短视频。 我也常刷到&#xff0c;从这类视频能看到点赞、收藏、评论的数据都特别高&#xff0c;动不动就几千、几…

【JAVA项目】基于jspm的【医院病历管理系统】

技术简介&#xff1a;采用jsp技术、MySQL等技术实现。 系统简介&#xff1a;通过标签分类管理等方式&#xff0c;实现管理员&#xff1b;个人中心、医院公告管理、用户管理、科室信息管理、医生管理、出诊信息管理、预约时间段管理、预约挂号管理、门诊病历管理、就诊评价管理、…

Oasis:首个可玩的AI生成互动游戏

游戏玩法介绍 Oasis 是由AI公司Decart开发的一款实时生成、可交互的Minecraft风格游戏。这款游戏利用生成式AI技术,创造出独特的“开放世界”体验。Oasis基于大量Minecraft游戏视频进行训练,通过键盘和鼠标输入实时生成游戏画面,模拟物理效果、规则及视觉效果。用户在游戏中…

Python网络爬虫入门篇!

预备知识 学习者需要预先掌握Python的数字类型、字符串类型、分支、循环、函数、列表类型、字典类型、文件和第三方库使用等概念和编程方法。 2. Python爬虫基本流程 a. 发送请求 使用http库向目标站点发起请求&#xff0c;即发送一个Request&#xff0c;Request包含&#xf…

【C++】踏上C++学习之旅(五):auto、范围for以及nullptr的精彩时刻(C++11)

文章目录 前言1. auto关键字&#xff08;C11&#xff09;1.1 为什么要有auto关键字1.2 auto关键字的使用方式1.3 auto的使用细则1.4 auto不能推导的场景 2. 基于范围的for循环&#xff08;C11&#xff09;2.1 范围for的语法2.2 范围for的使用条件 3. 指针空值nullptr&#xff0…

科研绘图系列:R语言组合多个不同图形(violin density barplot heatmap)

文章目录 介绍加载R包数据下载函数图1: Boxplots导入数据数据预处理画图图2: Violin导入数据数据预处理画图图3: Density plots per habitat数据预处理画图图4: Density plots per depth数据预处理画图图5: bar plot准备颜色导入数据数据预处理数据预处理画图图6: Mantel Heat…

系统聚类的分类数确定——聚合系数法

breast_cancer数据集分析——乳腺癌诊断 #读取乳腺癌数据 import pandas as pd import numpy as np from sklearn.datasets import load_breast_cancer data load_breast_cancer() X data.data y data.target.. _breast_cancer_dataset:Breast cancer wisconsin (diagnosti…

jsp+sevlet+mysql实现用户登陆和增删改查功能

jspsevletmysql实现用户登陆和增删改查功能 一、系统介绍二、功能展示1.用户登陆2.用户列表3.查询用户信息4.添加用户信息5.修改用户信息6.删除用户信息 四、其它1.其他系统实现 一、系统介绍 系统主要功能&#xff1a; 用户登陆、添加用户、查询用户、修改用户、删除用户 二…

一文了解Java序列化

Java 序列化&#xff08;Serialization&#xff09;是将对象的状态转换为字节流&#xff0c;以便将对象的状态保存到文件中或通过网络传输的过程。反序列化&#xff08;Deserialization&#xff09;则是将字节流恢复为原始对象。Java 序列化主要通过 Serializable 接口实现。 为…

斗破QT编程入门系列之前言:认识Qt:获取与安装(四星斗师)

本系列是在学习完C之后&#xff0c;然后通过Qt构建界面来&#xff0c;赋予枯燥的代码新的样貌&#xff0c;这样我们才能开发出更人性化的程序&#xff0c;同时会进一步提高初学者对编程的兴趣&#xff0c;大家加油&#xff0c;斗破Qt来了。 斗破Qt目录&#xff1a; 斗破Qt编程…

Spring Boot - 扩展点 EnvironmentPostProcessor源码分析及真实案例

文章目录 概述EnvironmentPostProcessor 作用EnvironmentPostProcessor 实现和注册创建类并实现接口注册到 Spring Boot常见应用场景 源码分析1. EnvironmentPostProcessor 接口定义2. 扩展点加载流程3. 加载 EnvironmentPostProcessor 实现类4. EnvironmentPostProcessor 执行…

封装的数字滚动组件的实现代码

效果&#xff1a; 学习啦&#xff1a; Vue 是一个渐进式框架&#xff0c;鼓励通过组件化来构建应用&#xff0c;其组件化优势&#xff1a; 代码复用&#xff1a;不同的视图和功能被封装成独立的组件&#xff0c;便于复用。易于维护&#xff1a;每个组件职责单一、耦合度低&…

Unity跨平台基本原理

目录 前言 ​编辑 Mono Unity和Mono的关系 Unity跨平台必备概念 Mono利用 Mono主要构成部分 基于Mono跨平台的优缺点 IL2CPP Mono和IL2CPP的区别 Mono IL2CPP Mono和IL2CPP的使用建议 安装IL2CPP IL2CPP打包存在的问题 类型裁剪 泛型问题 前言 Unity跨平台的基…

计算机网络(3)

UDP是面向无连接的通信协议&#xff0c;UDP数据包括目的端口号和源端口号信息&#xff0c;由于 不需要连接&#xff0c;所以可以实现广播发送&#xff1b; 传输控制层 UDP协议&#xff08;用户数据报协议&#xff09; UDP通信时不需要接收方确认&#xff0c;属于不可靠的传输&a…

2024年11月8日上海帆软用户大会

2024年11月8日上海帆软用户大会 2024年11月8日&#xff0c;上海成功举办了帆软用户大会&#xff0c;主题为“数字聚力&#xff0c;绽放新机”。大会汇聚了众多行业专家和企业代表&#xff0c;共同探讨数字化转型和商业智能领域的最新趋势和实践。 大会亮点&#xff1a; 专家…