最新要闻
- 国家外汇管理局:1-3月,中国外汇市场累计成交60.15万亿元|天天快资讯
- 每日速讯:iPhone 15系列换USB-C接口了!快充感人
- 环球即时:出城大片上演:多地道路拥堵
- 天天热头条丨手机销量大增41%!华为王者归来:一季度营收1321亿 涨了
- 密集落下!实拍北京多地突降冰雹:黑云压城
- 顶流“花花”提前休五一 保安大叔:和叶在值班
- 火车软卧是什么样子的(火车软卧)
- 【环球速看料】柞水终南山寨一日游攻略(终南山寨在什么地方)
- 不靠氪金 价格卷死同行:逆水寒手游开启二测多次冲上热搜:预约超3000万
- 好友田启文爆料周星驰或将于65岁重返大银幕!自导自演、阵容空前-短讯
- 抗衡奔驰E级 全新宝马5系无伪谍照首曝:大鸡腿档杆成历史
- 比马斯克的猎鹰还强10倍?俄罗斯自研火箭将可重复使用100次 天天热点
- 蔚来起诉抖音大V造谣侵权:索赔200万
- 环球观点:中科氢量平通仪好不好(中科氢量平通仪)
- 当AI遇上AD,腾讯信息流广告行业的智能化营销前景如何?-世界通讯
- 环球观速讯丨“3nm EUV”工艺稳了 Intel明年上半年出货144核至强处理器:超越Zen4
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
最新资讯:题目 3158: 蓝桥杯2023年第十四届省赛真题-三国游戏(贪心)
【资料图】
题目描述
小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i 个事件发生时会分别让 X, Y, Z 增加Ai , Bi ,Ci 。当游戏结束时 (所有事件的发生与否已经确定),如果 X, Y, Z 的其中一个大于另外两个之和,我们认为其获胜。例如,当 X > Y + Z 时,我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜,最多发生了多少个事件?如果不存在任何能让某国获胜的情况,请输出 −1 。
输入格式
输入的第一行包含一个整数 n 。第二行包含 n 个整数表示 Ai,相邻整数之间使用一个空格分隔。第三行包含 n 个整数表示 Bi,相邻整数之间使用一个空格分隔。第四行包含 n 个整数表示 Ci,相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。样例输入31 2 22 3 21 0 7样例输出2
解答
1.解题思路是,使用贪心思想选出三个国家各自获胜的最大事件数,取其最大作为答案;那么如何算出一个国家士兵应该经历哪些事件并满足大于另外两国呢,同样使用贪心算法2.我们使用一个类来存储一个事件,这个事件有abc三个属性,分别对应题目对三个国家兵力的提升
static class node { long a, b, c; public node(long a, long b, long c) { this.a = a; this.b = b; this.c = c; } }
那么我们输入数据时需要注意一点,它的每一行都是对一个国家的影响,也就是对于事件i,输入的第一行数据是事件i的a,第二行数据才是事件i的b
node[] events = new node[n]; for (int i = 0; i < n; i++) events[i] = new node(sc.nextInt(), 0, 0); for (int i = 0; i < n; i++) events[i].b = sc.nextInt(); for (int i = 0; i < n; i++) events[i].c = sc.nextInt();
3.我们对事件进行排序,排序规则根据我们的需求而定,我们需要得出每个国家获胜的事件数,就把事件排序为对那个国家提升的兵力最多的事件最靠前比如1 2 22 3 21 0 7事件i1对第一个国家提升量为-2,而i2提升量为-1,i3提升量为-7,则排序为i2i1i3事件i1对第二个国家提升量为0,而i2提升量为1,i3提升量为-7,则排序为i2i1i3事件i1对第三个国家提升量为-2,而i2提升量为-5,i3提升量为3,则排序为i3i1i2
Arrays.sort(events, (o1, o2) -> o2.a - o2.b - o2.c + o1.b + o1.c - o1.a > 0 ? 1 : -1); Arrays.sort(events, (o1, o2) -> o2.b - o2.a - o2.c + o1.a + o1.c - o1.b > 0 ? 1 : -1); Arrays.sort(events, (o1, o2) -> o2.c - o2.a - o2.b + o1.a + o1.b - o1.c > 0 ? 1 : -1);
排序完之后使用排序后的顺序算出对应国家在最大优势的情况下可以经过几个事件并满足兵力大于其他两国
Arrays.sort(events, (o1, o2) -> o2.a - o2.b - o2.c + o1.b + o1.c - o1.a > 0 ? 1 : -1); ans = Math.max(ans, f(events, 0)); Arrays.sort(events, (o1, o2) -> o2.b - o2.a - o2.c + o1.a + o1.c - o1.b > 0 ? 1 : -1); ans = Math.max(ans, f(events, 1)); Arrays.sort(events, (o1, o2) -> o2.c - o2.a - o2.b + o1.a + o1.b - o1.c > 0 ? 1 : -1); ans = Math.max(ans, f(events, 2));
这里使用一个数字标记当前优势国,而且如果你不能在第一个事件就大于其他两国,那么后面就更不可能了,所以不满足a>b+c时就直接break并返回事件数
private static long f(node[] events, int cur) { long a = 0, b = 0, c = 0; long res = 0; for (int i = 0; i < events.length; i++) { a += events[i].a; b += events[i].b; c += events[i].c; if (cur == 0) { if (a > b + c) { res = i + 1; } else { break; } } else if (cur == 1) { if (b > a + c) { res = i + 1; } else { break; } } else { if (c > b + a) { res = i + 1; } else { break; } } } return res; }
4.最后打印答案,如果事件数为0,说明没有国家能够满足a>b+c的条件打印-1即可
System.out.println(ans == 0 ? -1 : ans);
完整代码
import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long ans = 0; node[] events = new node[n]; for (int i = 0; i < n; i++) events[i] = new node(sc.nextInt(), 0, 0); for (int i = 0; i < n; i++) events[i].b = sc.nextInt(); for (int i = 0; i < n; i++) events[i].c = sc.nextInt(); Arrays.sort(events, (o1, o2) -> o2.a - o2.b - o2.c + o1.b + o1.c - o1.a > 0 ? 1 : -1); ans = Math.max(ans, f(events, 0)); Arrays.sort(events, (o1, o2) -> o2.b - o2.a - o2.c + o1.a + o1.c - o1.b > 0 ? 1 : -1); ans = Math.max(ans, f(events, 1)); Arrays.sort(events, (o1, o2) -> o2.c - o2.a - o2.b + o1.a + o1.b - o1.c > 0 ? 1 : -1); ans = Math.max(ans, f(events, 2)); System.out.println(ans == 0 ? -1 : ans); } private static long f(node[] events, int cur) { long a = 0, b = 0, c = 0; long res = 0; for (int i = 0; i < events.length; i++) { a += events[i].a; b += events[i].b; c += events[i].c; if (cur == 0) { if (a > b + c) { res = i + 1; } else { break; } } else if (cur == 1) { if (b > a + c) { res = i + 1; } else { break; } } else { if (c > b + a) { res = i + 1; } else { break; } } } return res; } static class node { long a, b, c; public node(long a, long b, long c) { this.a = a; this.b = b; this.c = c; } }}
关键词:
-
银河麒麟V10系统安装Redis|环球观点
原文链接:https: www cnblogs com liunaixu p 17138335 html一、准备工作安装环境:银河麒麟KylinV101、Re
来源: 软件开发所有文档合集下载 全球今亮点
最新资讯:题目 3158: 蓝桥杯2023年第十四届省赛真题-三国游戏(贪心)
美团一面:如何实现一个100W ops 生产者消费者程序?
银河麒麟V10系统安装Redis|环球观点
vue3 + ts + vite 封装 request 每日热议
焦点关注:商品日报(4月28日):黑色系疲软焦煤大跌近4% 红枣收涨近4%
国家外汇管理局:1-3月,中国外汇市场累计成交60.15万亿元|天天快资讯
每日速讯:iPhone 15系列换USB-C接口了!快充感人
环球即时:出城大片上演:多地道路拥堵
天天热头条丨手机销量大增41%!华为王者归来:一季度营收1321亿 涨了
密集落下!实拍北京多地突降冰雹:黑云压城
顶流“花花”提前休五一 保安大叔:和叶在值班
火车软卧是什么样子的(火车软卧)
用 ChatGPT 写代码,效率杠杠的! 实时
一文看懂低代码,5分钟从入门到原理全搞定 环球热文
论并行,并发,同步,异步之间的联系与区别-天天实时
【环球速看料】柞水终南山寨一日游攻略(终南山寨在什么地方)
中信建投国家电投新能源REIT获原始权益人增持3200万份
天天快资讯丨【财经分析】IPv6如何从“能用”转向“好用”“爱用”?
不靠氪金 价格卷死同行:逆水寒手游开启二测多次冲上热搜:预约超3000万
好友田启文爆料周星驰或将于65岁重返大银幕!自导自演、阵容空前-短讯
抗衡奔驰E级 全新宝马5系无伪谍照首曝:大鸡腿档杆成历史
比马斯克的猎鹰还强10倍?俄罗斯自研火箭将可重复使用100次 天天热点
蔚来起诉抖音大V造谣侵权:索赔200万
环球观点:中科氢量平通仪好不好(中科氢量平通仪)
python的绘图工具matplotlib.pyplot-环球报资讯
App Store上架流程/苹果app发布流程 全球快播
当AI遇上AD,腾讯信息流广告行业的智能化营销前景如何?-世界通讯
环球观速讯丨“3nm EUV”工艺稳了 Intel明年上半年出货144核至强处理器:超越Zen4
明天五一!滴滴副总裁李敏:今晚高峰打车不容易 成功率可能不足50%|全球新动态
成都一民宿推出“36元睡客厅躺椅”服务:已被预订一空
环球百事通!100%纯棉!雅鹿男士背心2件只要29元
1L体积塞进电源!联想小新mini主机开启预售:3699元起
轻松脱眉毛下垂的方法是什么
二分查找算法讲解及其C++代码实现 天天聚看点
世界今日报丨相亲成功率100%!技术大佬都在用的SWOT模型【No.3】
当前播报:generate什么意思_generate是什么意思呢
全球关注:特斯拉:不要相信马斯克对自动驾驶的宣传、可能是假的
5月26上映!《小美人鱼》女主全球爆火 黑小美人鱼晒新海报原来这么美? 最新消息
锦州师范学院地址在哪里 锦州师范学院
这两个重载方法,你怎么重构?
民航今天预计发送旅客208万人次
ChatGPT成必备技能!超九成企业想雇佣了解ChatGPT的员工
【全球播资讯】性能提升36%!Surface Laptop 5评测:Windows阵营最精致优雅的轻薄本
搭载全新12代i3八核处理器轻薄本仅2999元!攀升笔记本超级秒杀
手机摆动跳广告判了!大学生起诉美图秀秀获赔1元
视点!国外车主吐槽新特斯拉Model S做工差:对不起这价格
每日快播:华为P60可支持5G了 只要640元
视焦点讯!博弈论入门
定了!“五一”期间,这些行为不予处罚|今日讯
首发6nm天玑8020芯片!荣耀平板V8发布:1799元起
日本东电坚持福岛核污染水排海计划不变:总量约133万吨|全球热资讯
当前看点!40年Microsoft品牌再见!Suface全面接棒微软配件市场
各个大长腿超短裙吸睛:淄博一群175美少女接送游客非官方行为 天天热点评
热门看点:首款百万售价比亚迪!仰望U8动力信息曝光:纯电180km、零百最快3.6s
亚洲有多少个国家?亚洲最好的大学是哪个?亚洲哪个国家最干净?
全球新资讯:无锡口腔医院价格表
进击的巨人真相是什么?进击的巨人最终季大结局
武林外传为什么那么火?武林外传为什么不拍第二部?
为什么这么多人喜欢海绵宝宝?为什么海绵宝宝里的章鱼哥总是不开心?
猫咪为什么不喜欢橘子味?橘猫为什么体型那么大?
qq炫舞炫彩宝石怎么获得?qq炫舞炫彩宝石有什么用?
IM开发干货分享:IM客户端不同版本兼容运行的技术思路和实践总结
简单渗透测试流程-环球观速讯
天天快资讯:AIRIOT助力城市管廊工程,智慧物联守护城市生命线
全球速讯:[Termux]更换Termux源 安装Debian容器并 设置Debian镜像源且 安装code-server(附安卓/APK安装包+下载源+lan
笔记本gt630m相当于什么核显?笔记本GT630M显卡怎么样?
梦幻西游2需要点卡吗?梦幻西游2023新区开服表
IBMThinkPad笔记本电脑怎么一键还原?IBMThinkPad笔记本电脑怎么开机?
岳阳楼下诵经典|全球今日讯
大连市长城宽带DNS是多少?大连市长城宽带资费表
当前观察:硬盘预读参数变化分析
继烧烤后淄博代购也火了:网友都很想去
“五一”假期高速免费五天!提前出发的过省界收费站时注意时间 环球快播报
今日讯!五一这些景点门票已约满:游客注意别跑空
3200RPM超高转速 满速运转还不抖!酷冷至尊莫比乌斯120 OC风扇评测 环球报资讯
科幻工业风!红魔电竞显示器银翼版来了:极窄边框设计 热点评
贵阳市档案馆通过全国示范数字档案馆测试
Linux恢复文件双手锏|全球即时
世界热讯:基于Java开发的数字知识库,支持全文检索、知识图谱和工作流审批,太强大了
微资讯!聊一聊GIS之家团队数据案例源码共享以及在线体验
当前热讯:JasperReports教程_编程入门自学教程_菜鸟教程-免费教程分享
安装Amos结构方程模型分析软件的方法 环球热闻
兴齐眼药去年四季度起利润急降:“近视神药”网售被禁影响显现,正式上市时市场恐已成红海
7项技术行业唯一!vivo X Fold2今日首销:8999元起
五一档票房第一!王一博电影《长空之王》今日上映:歼-20真机硬核亮相_世界热头条
热议:四川瓦屋山首次发现猛禽之王:自然界顶级掠食者 海拔4000米以上活动
60架C919和40架ARJ21!海航豪购100架国产飞机 环球微头条
小鹏G6创意视频被指“侮辱科学家” 创作者发声:绝非侮辱而是致敬
证监会:下月公布虚拟交易平台发牌框架
每日聚焦:Docker获取Let`s Encrypt SSL 证书
天天热讯:【策略设计模式详解】C/Java/JS/Go/Python/TS不同语言实现
一季度新接船舶订单量同比增53%(新数据 新看点) 环球看热讯
Win10再见!微软确认22H2为终极正式版 系统不再更新:2025年结束支持
价保618!真我GT Neo5降了:1TB版卖3299元 世界快报
比Wi-Fi 6快4倍!华为首测Wi-Fi 7:真机网速狂飙4.3Gbps 当前热门
全球快看:越来越黑化!《变形金刚1-7》女主角颜值变化 网友叹息黑人赢麻了
天风证券:4月第3周新能源汽车订单明显改善,车展有望带动终端需求回升
“欧佩克+”减产倒计时 中国能源供给如何摆脱新变数|环球今亮点
天天热文:北大校训是什么(北京大学的校训是什么)