【寒假每日一题·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…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

