题目 3158: 蓝桥杯2023年第十四届省赛真题-三国游戏(贪心)

这篇具有很好参考价值的文章主要介绍了题目 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,相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。
样例输入
3
1 2 2
2 3 2
1 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 2
2 3 2
1 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即可文章来源地址https://www.toymoban.com/news/detail-428153.html

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;
        }
    }
}

到了这里,关于题目 3158: 蓝桥杯2023年第十四届省赛真题-三国游戏(贪心)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯嵌入式第十四届省赛题目解析

    前几天刚刚参加完第十四届的省赛,这届题目比我想象中的要难,其实想一想这也是应该的,以前的知识点都被摸透了,也是需要加入新的知识点了,但是我还是想说能不能别在我参加的时候加大题目难度啊。 不过听说隔壁单片机的省赛都比往年的国赛还难,这就有点离谱了

    2024年02月06日
    浏览(58)
  • 蓝桥杯单片机第十四届省赛题目和程序答案

    目录  1、前言  2、题目 3、程序架构     3.1 display.c    3.2 ds1302.c    3.3 iic.c    3.4 onewire.c    3.5 main.c 主函数文件    3.6 环境配置 4. 历年蓝桥杯单片机试题和答案        抽空复习了一下,拿下单片机省赛一等奖,在此分享一下最新的14届省赛程序设计答案          模

    2024年02月06日
    浏览(162)
  • 2023年第十四届蓝桥杯省赛Java C组题解

    只做出来(ACDFGH),挑几个出来,答案不一定正确,但自己测试通过了 求1~20230408的和 这里就直接套等差数列的求和公式,答案:204634714038436   【问题描述】         有一个长度为n的数组(n是10的倍数),每个数 Ai 都是区间[0,9]中的整数,小明发现数组里每种数出现的次数不太

    2023年04月26日
    浏览(40)
  • 2023年第十四届蓝桥杯大赛python组省赛真题(已更新完)

    本篇更新蓝桥杯省赛真题的后5道。 6.试题 F: 公因数匹配 时间限制: 10.0s 内存限制: 512.0MB 本题总分:15 分 【问题描述】 给定 n 个正整数 Ai,请找出两个数 i, j 使得 i j 且 Ai 和 Aj 存在大于 1 的 公因数。 如果存在多组 i, j,请输出 i 最小的那组。如果仍然存在多组 i, j,请输出

    2024年02月06日
    浏览(65)
  • 2023年第十四届蓝桥杯JAVA B组题目

    第二次参加蓝桥杯,手机再次没电导致只写了两个半小时就交了(不能重复交哎),这次带了充电宝,结果充电宝充电线中途松了,不得不说腾讯会议的耗电量真大。本博客就是刚提交后写的,可以看看时间hhh。 就做了前五道题,不过前五道题就搜索、枚举、进制就能做和一

    2023年04月09日
    浏览(43)
  • 2023年第十四届蓝桥杯Web应用开发(职业院校组)省赛真题

    前言: 因博主申请的线上考试所以留下了真题,本篇文章只有题目没有答案( 真题源码资源在最后 ),因博主技术有限(请理解一下),博主只拿了省二 目录 1. 电影院排座位 2. 图⽚⽔印⽣成: 3.  收集帛书碎⽚ 4. ⾃适应⻚⾯ 5.  外卖给好评 6. 视频弹幕  7. ISBN 转换与⽣成

    2024年02月05日
    浏览(49)
  • 2023年第十四届蓝桥杯单片机开放与设计省赛微析与经验分享

    前言:        2023年4月8日, 就在昨天,本人刚参与了第十四届蓝桥杯单片机开放与设计省赛。         整体做下来,且不谈客观题,今年的程序题,个人感觉有点像大杂烩,题量大,细节多,而且有些要求定义不够清晰,所以本人这次做的不够完美,并且因为时间问题有

    2024年02月08日
    浏览(56)
  • 蓝桥杯第十四届省赛完整题解 C/C++ B组

    没有测评,不知道对不对,仅仅过样例而已 本题总分:5 分 【问题描述】 小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的 范围之内。数组中的元素从左至右如下所示: 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9

    2023年04月13日
    浏览(50)
  • 【蓝桥杯嵌入式】蓝桥杯嵌入式第十四届省赛程序真题,真题分析与代码讲解

     🎊【蓝桥杯嵌入式】专题正在持续更新中,原理图解析✨,各模块分析✨以及历年真题讲解✨都已更新完毕,欢迎大家前往订阅本专题🎏 🎏【蓝桥杯嵌入式】蓝桥杯第十届省赛真题 🎏【蓝桥杯嵌入式】蓝桥杯第十二届省赛程序真题 🎏【蓝桥杯嵌入式】蓝桥杯第十三届省

    2023年04月15日
    浏览(103)
  • 2023年第十四届蓝桥杯Java_大学B组真题

    【考生须知】 考试开始后,选手首先下载题目,并使用考场现场公布的解压密码解压试 题。 考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案,被浏览的答案允许拷贝。时间截止后,将无法继续提交或浏览答案。 对同一题目,选手可多次提交答案,以最后一次提

    2023年04月11日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包