【寒假每日一题·2024】AcWing 4965. 三国游戏(补)
文章目录
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
一、题目
1、原题链接
4965. 三国游戏
2、题目描述
二、解题报告
1、思路分析
思路参考y总:y总讲解视频
(1)题目中的获胜情况分为三种:魏国胜(兵量为X)、蜀国胜(兵量为Y)、吴国胜(兵量为Z)。以魏国胜为例,需要使得X>Y+Z,也就是需要使得X-Y-Z>0,记W=X-Y-Z,即W>0,W初始为0(因为X、Y、Z初始均为0)。
(2)由于每个事件都会使X,Y,Z分别增加A[i]、B[i]、C[i]。记V[i]=A[i]-B[i]-C[i],即每个事件会使W增加V[i]。所以题目就可以转化为最多多少个事件(也就是对W加最多多少次不同的V[i])可以使W保持大于0(也就是这些事件的每个V[i]之和大于0)。
(3)可以将V数组进行从大到小排序,由于W初始为0,所以当发生V[i]>0的事件发生最多的情况下发生的事件最多的情况为最优解。所以大到小依次枚举V[i],并同时记录当前发生事件数和到目前枚举到的V[i]之和,若出现总和不大于0时,说明此时已经不是最优解,最优解即为除去当前事件,前面所有事件均发生的情况。
(4)依据相同思路,依次求出蜀国、吴国获胜时的最大发生事件数,取最大值即可,若不存在让任何一国获胜的情况,按题目要求输出即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N], b[N], c[N];
int v[N];
bool cmp(int A ,int B) {return A > B;
}
//x[]为获胜国的事件产生效果,y[]、z[]为未获胜国的
int solve(int x[], int y[], int z[]) {for (int i = 0; i < n; i++) {v[i] = x[i] - y[i] - z[i];}sort(v, v + n, cmp);//注:可能会超intlong long sum = 0, cnt = 0; //sum记录当前枚举到V[i]的总和,cnt记录发生事件数for (int i = 0; i < n; i++) {sum += v[i];if (sum > 0) cnt++;else break;} return cnt;
}
int main() {cin >> n;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < n; i++) cin >> b[i];for (int i = 0; i < n; i++) cin >> c[i];int res = 0;int num1 = solve(a, b, c);int num2 = solve(b, a, c);int num3 = solve(c, a, b);//取三种情况最大值res = max(max(num1, num2), num3);if (res) cout << res;else cout << -1; //若不存在,则输出-1return 0;
}
相关文章:
【寒假每日一题·2024】AcWing 4965. 三国游戏(补)
文章目录 一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 一、题目 1、原题链接 4965. 三国游戏 2、题目描述 二、解题报告 1、思路分析 思路参考y总:y总讲解视频 (1)题目中的获胜情况分为三种ÿ…...
docker 安装mongodb 数据库
1.拉取mongodb镜像 docker pull mongo2.创建文件夹 mkdir -p /home/mongo/conf/ mkdir -p /home/mongo/data/ mkdir -p /home/mongo/logs/3.新增mongod.conf文件 cd /home/mongo/conf && vi mongod.confmongod.conf文件内容: # 数据库文件存储位置 dbpa…...
整数反转算法(leetcode第7题)
题目描述: 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。假设环境不允许存储 64 位整数(有符号或无符号)。示例 1…...
微信小程序(十)表单组件(入门)
注释很详细,直接上代码 上一篇 新增内容: 1.type 属性指定表单类型 2.placeholder 属性指定输入框为空时的占位文字 源码: form.wxml <!-- 提前准备好的布局结构代码 --> <view class"register"><view class"…...
xcode 设置 ios苹果图标,为Flutter应用程序配置iOS图标
图标设置 1,根据图片构建各类尺寸的图标2.xcode打开ios文件3.xcode设置图标4.打包提交审核,即可(打包教程可通过我的主页查找) 1,根据图片构建各类尺寸的图标 工具网址:https://icon.wuruihong.com/ 下载之后文件目录如下 拷贝到项目的ios\Runner\Assets.xcassets\AppIcon.ap…...
什么是IDE?新手用哪个IDE比较好?
哈喽大家好,我是咕噜美乐蒂,很高兴又见面啦!今天我们来了解一下什么是IDE以及新手应该如何选择IDE比较合适。 一、什么是IDE? IDE(Integrated Development Environment,集成开发环境)是一种软…...
【数据库学习】pg安装与运维
1,安装与配置 #安装 yum install https:....rpm1)安装目录 bin目录:二进制可执行文件目录,此目录下有postgres、psql等可执行程序;pg_ctl工具在此目录,可以通过pg_ctl --help查看具体使用。 conf目录&…...
第二篇【传奇开心果短博文系列】Python的OpenCV库技术点案例示例:图像处理
传奇开心果短博文系列 系列短博文目录Python的OpenCV库技术点案例示例短博文系列 博文目录一、项目目标二、第一个示例代码三、第二个示例代码四、第三个示例代码五、第四个示例代码六、第五个示例代码七、知识点归纳总结 系列短博文目录 Python的OpenCV库技术点案例示例短博文…...
【vue oidc-client】invalid_requestRequest Id: 0HN0OOPFRLSF2:00000002
需求:完成统一登录,需要从三方平台跳到我们的平台。 oidc-client报错记录。这个一般是配置信息出错,需要和三方平台进行沟通,一定要把client_id,密钥进行对应; 同时关于此次出错还修改了以下代码ÿ…...
什么是中间人攻击? ssh 连接出现 Host key verification failed 解决方法
文章目录 前言known_hosts 文件是什么文件路径示例 连接出现 Host key verification failedssh-keygen -R [hostname or ip address]删除整个 known_hosts 文件 其它聊聊中间人攻击ssh 如何保证安全?加密流程漏洞在哪里如何避免中间人攻击 个人简介 前言 最近服务器…...
数据结构系统刷题
本文为系统刷leetcode的记录,会记录自己根据代码随想录刷过的leetcode,方便直接点开刷题,时常更新 时间复杂度简记为s 空间复杂度简记为k 数组 704 二分查找 一维二分查找 (1)[left, right] class Solution { publi…...
【RabbitMQ】延迟队列之死信交换机
🎉🎉欢迎来到我的CSDN主页!🎉🎉 🏅我是Java方文山,一个在CSDN分享笔记的博主。📚📚 🌟推荐给大家我的专栏《RabbitMQ实战》。🎯🎯 &am…...
2024交通运输工程与土木建筑工程国际会议(ICTECCE2024)
2024交通运输工程与土木建筑工程国际会议(ICTECCE2024) 会议简介 2024年国际交通工程和土木建筑工程会议(ICTECCE 2024)将在中国杭州举行。ICTECCE 2024致力于为交通工程和土木工程材料领域的学者、工程师和研究人员提供一个大型学术交流平台和双向交流…...
搜索引擎Elasticsearch了解
1.Lucene 是什么? 2.模块介绍 Lucene是什么: 一种高性能,可伸缩的信息搜索(IR)库 在2000年开源,最初由鼎鼎大名的Doug Cutting开发 是基于Java实现的高性能的开源项目 Lucene采用了基于倒排表的设计原理,可以非常高效地实现文本查找,在底层采用了分段的存储模式,使它在读…...
【操作系统基础】【CPU访存原理】:寄存 缓存 内存 外存、内存空间分区、虚拟地址转换、虚拟地址的映射
存储器怎么存储数据、内存空间分区、虚拟地址转换 计算机的存储器:寄存 缓存 内存 外存(按功能划分) 计算机的处理器需要一个存储器来存储大量的指令和数据以便自己不断取指执行和访问数据。 内存(内存就是运行内存,…...
windows下git pull超时,ping不通github
报错 ssh: connect to host github.com port 22: Connection timed out fatal: Could not read from remote repository. Please make sure you have the correct access rights and the repository exists. 解决办法 修改hosts 最后加一行,文件位置:…...
springboot快速写接口
1. 建proj形式 name会变成文件夹的名字,相当于你的项目名称 基础包 2. 基础依赖 3. 配置数据库 这里要打开mysql,并且创建数据库 方法: 安装好数据库,改好账号密码用navicat来建表和账号配置properties.yml文件即可 4.用res…...
数据结构排序算详解(动态图+代码描述)
目录 1、直接插入排序(升序) 2、希尔排序(升序) 3、选择排序(升序) 方式一(一个指针) 方式二(两个指针) 4、堆排序(升序) 5、冒…...
2024-01-25 力扣高频SQL50题目1174. 即时食物配送
题目如下: 配送表: Delivery -------------------------------------- | Column Name | Type | -------------------------------------- | delivery_id | int | | customer_id | int | | order_date…...
java web 校园健康管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
一、源码特点 java Web校园健康管理系统是一套完善的java web信息管理系统 ,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发,数据库为Mysq…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...

