三国游戏(第十四届蓝桥杯)
题目
小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z(一开始可以认为都为 0)。
游戏有 n个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i个事件发生时会分别让 X,Y,Z
增加 A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci。
当游戏结束时 (所有事件的发生与否已经确定),如果 X,Y,Z的其中一个大于另外两个之和,我们认为其获胜。
例如,当 X>Y+Z时,我们认为魏国获胜。
小蓝想知道游戏结束时如果有其中一个国家获胜,最多发生了多少个事件?
如果不存在任何能让某国获胜的情况,请输出 −1。
输入格式
输入的第一行包含一个整数 n。
第二行包含 n个整数表示 A i A_i Ai,相邻整数之间使用一个空格分隔。
第三行包含 n个整数表示 B i B_i Bi,相邻整数之间使用一个空格分隔。
第四行包含 n 个整数表示 C i C_i Ci,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40%的评测用例,n≤500;
对于 70%的评测用例,n≤5000;
对于所有评测用例, 1 ≤ n ≤ 1 0 5 , 0 ≤ A i , B i , C i ≤ 1 0 9 1≤n≤10^5,0≤A_i,B_i,C_i≤10^9 1≤n≤105,0≤Ai,Bi,Ci≤109。
注意,蓝桥杯官方给出的关于 A i , B i , C i A_i,B_i,C_i Ai,Bi,Ci
的数据范围是 1 ≤ A i , B i , C i ≤ 1 0 9 1≤Ai,Bi,Ci≤10^9 1≤Ai,Bi,Ci≤109,但是这与给出的输入样例相矛盾,因此予以纠正。
输入样例:
3
1 2 2
2 3 2
1 0 7
输出样例:
2
样例解释
发生两个事件时,有两种不同的情况会出现获胜方。
发生 1,2 事件时蜀国获胜。
发生 1,3 事件时吴国获胜。
代码(python版本)
n=int(input())
def check(x,y,z)->int:w=[]for i in range(n):w.append(x[i]-y[i]-z[i])w.sort(reverse=True)res=-1sum=0for i in range(n):sum+=w[i]if sum>0:res=i+1return res
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
print(max(check(a,b,c),check(b,a,c),check(c,a,b)))
代码(cpp版本)
代码先欠着
思路:
本题是一道贪心题。当我一开始看这个题目的时候,首先想到的就是一道dfs题,但是当我看到数据范围为 1 0 5 10^5 105的时候我直接人傻,这还怎么dfs。于是换一个思路。
首先因为这个数据范围是 1 0 5 10^5 105,那么我们需要将时间复杂度控制在 n l o g n nlogn nlogn中。
本题要求的是一个国家打赢两个国家最多能发生多少次事件,看到最多,我就感觉是一道贪心题,那么怎么贪心呢?
首先我们需要想明白怎么贪?那我们可以先假设三个国家分别是ABC,然后我们假设 A > B + C A>B+C A>B+C,那么ABC到底是哪三个国家呢?这个直接可以枚举出来,A是魏蜀吴三个其中之一,剩下的B和C就是除了A以外的两个国家。
那么我们可以写一个函数来判断 A > B + C A>B+C A>B+C最多能要多少次
那么我们可以遍历ABC三个数组,然后用一个数组W来接受一下A国和B+C国的兵力差,也就是W[i]=A[i]-B[i]-C[i]的值,那么W[i]的含义是什么呢?很明显当W[i]>0的时候说明A的兵力比B+C的要多,这个事件我们当然要选。然后进行排序,接下来就是每次都获取到当前的兵力。然后用一个sum来记录,sum代表的是什么意思呢,就是A当前比B+C多sum个兵,然后我们依次进行遍历,sum不断累加W[i],当sum累加当前的兵力之后还是大于零,说明当前的事件容许发生,这时候就该让res++了。直到sum小于0的时候就不行了。
然后我们来看这个思路,整个的时间复杂度正好是 n l o g n nlogn nlogn(sort的时间复杂度)。
最后我们只需要调用上面的函数三次即可,也就是check(魏,蜀,吴),check(蜀,魏,吴),check(吴,蜀,魏),然后三者取最大值就行。
相关文章:
三国游戏(第十四届蓝桥杯)
题目 小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z(一开始可以认为都为 0)。 游戏有 n个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i个事件发生时会分别让 X,Y,Z 增加 A i , B…...

k8s---包管理器helm
内容预知 目录 内容预知 helm相关知识 Helm的简介与了解 helm的三个重要概念 helm的安装和使用 将软件包拖入master01上 使用 helm 安装 Chart 对chart的基本使用 查看chart信息 安装chart 对chart的基本管理 helm自定义模板 在镜像仓库中拉取chart,查…...

对于超低延迟SSD,IO调度器已经过时了吗?-part2
为了进行这项研究,他们设计了一套严谨的实验方法论,包括在配备了高速Intel Optane P4801X Series NVMe SSD的服务器上执行一系列微观和宏观基准测试,同时监测系统能耗情况。这些测试涵盖了多种工作负载场景,从单一进程提交大量请求…...

【C++】list的使用
目录 1 构造1.1 无参构造1.2 构造的list中包含n个值为val的元素1.3 用[first, last)区间中的元素构造list1.4 拷贝构造 2 迭代器的使用2.1 begin end2.2 rbegin rend 3 容量操作3.1 empty size 4 获取元素4.1 front back 5 插入、删除、修改5.1 头插-push_front和尾插-push…...

mybatis的缓存机制
视频教程_免费高速下载|百度网盘-分享无限制 (baidu.com) MyBatis 有一套灵活而强大的缓存机制,主要分为两级缓存:一级缓存(本地缓存)和二级缓存(全局缓存)。 一级缓存(本地缓存)&a…...

ChatGLM3报错:No chat template is defined for this tokenizer
使用官方提供的脚本创建ChatGLM3的DEMO: cd basic_demo python web_demo_gradio.py 出现效果异常问题: conversation [{role: user, content: 你好}, {role: assistant, content: 你好,有什么我可以帮助你的吗?\n\n<|im_end|…...
大数据学习之Flink、搞懂Flink的恢复策略
第一章、Flink的容错机制 第二章、Flink核心组件和工作原理 第三章、Flink的恢复策略 第四章、Flink容错机制的注意事项 第五章、Flink的容错机制与其他框架的容错机制相比较 目录 第三章、Flink的恢复策略 Ⅰ、恢复策略 1. Checkpoint: 2. Savepoint&#…...
C语言易忘操作符全集
目录 位操作符 1.按位与(&) 2.按位或(|) 3.按位异或(^) 4.按位取反(~) 5.左移(<<) 6.右移(>>) 逻辑操作符 1.逻辑与(&&) 2.逻辑或(||) 3.逻辑非(!) 位操作符 1.按位与(…...
网络请求 mvp mvvm get post delete put 请求
get 参数拼接 如下接口 localhost:8080/uav/plotting/page/app?pageNum1&pageSize10&appIde3c59e28-2032-4ddf-a762-7cec96f772a4&orgId65&plottingTypepoint GET("https:/uav/plotting/page/app") Observable<PlotList.DataBean> allPoin…...
研究生开题报告撰写:文言一心VSChatgpt3.5
文言一心 问:我是一名研二学生,请帮我生成一份研究生毕设开题答辩ppt框架。 答:好的,以下是一份研究生毕设开题答辩PPT的框架,供您参考: 幻灯片1:封面页 标题:研究生毕设开题答辩…...

Unity animator动画倒放的方法
在Unity中, 我们有时候不仅需要animator正放的效果,也需要倒放的效果。但我们在实际制作动画的时候可以只制作一个正放的动画,然后通过代码控制倒放。 实现方法其实很简单,只需要把animator动画的speed设置为-1即为倒放ÿ…...

Dubbo源码解析第一期:如何使用Netty4构建RPC
一、背景 早期学习和使用Dubbo的时候(那时候Dubbo还没成为Apache顶级项目),写过一些源码解读,但随着Dubbo发生了翻天覆地的变化,那些文章早已过时,所以现在计划针对最新的Apache Dubbo源码来进行“阅读理解…...

unity刷新grid,列表
获取UIGrid 组件,更新列表 listParent.GetComponent().repositionNow true;...

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图)
目录 🌈前言: 📁 高精度的概念 📁 高精度加法和其模板 📁 高精度减法和其模板 📁 高精度乘法和其模板 📁 高精度除法和其模板 📁 总结 🌈前言: 这篇文…...
人形机器人创新发展顶层设计与关键技术布局
系列文章目录 前言 随着新一轮科技革命和产业变革的深入推进,我国高度重视人形机器人的创新发展,提出了一系列具有前瞻性和战略性的指导意见。规划指出,到2025年,我国将初步建立人形机器人创新体系,攻克“大脑”、“小…...

C语言-算法-最小生成树
【模板】最小生成树 题目描述 如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz。 输入格式 第一行包含两个整数 N , M N,M N,M,表示该图共有 N N N 个结点和 M M M 条无向边。 接下来 M M M 行…...
android 扫描某个包下的所有类
注意事项 如果在用Android Studio开发过程中,如果新增了类,扫描不到。只能把APP卸载了,才能扫描到。 可能是Instance Run 的影响。 后面研究一下这篇文章,看看能不能解决 Android 遍历Apk下的所有类文件 package com.trs.nmip.…...
远程ssh 不通的原因之一
背景:我都想大喊一声,我上网是通的, ping网址是通的,ping www.baidu.com 是通的, 怎么都远程不了,报超时;嘿, 别人远程就能行。我都想挠头了。 目录 1. 先 ping 自己,…...

wamp集成环境部署
Windows下Apache服务器搭建 第一步:下载Windows下的最新ZIP压缩包 推荐下载网址:http://www.apachelounge.com/download/ 为了让Apache服务器发挥更好的性能,请根据自己的系统选择下载,如果不清楚自己的系统是64位还是32位&am…...
使用antd design pro 及后端nodejs express 结合minio进行文件的上传和下载管理
使用Ant Design Pro前端框架结合Node.js Express后端服务以及MinIO作为对象存储,实现文件上传和下载管理的基本步骤如下: 1. 安装所需依赖 在Node.js Express项目中安装minio客户端库: npm install minio --save 在前端项目(假…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...

如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...