题解 | #E. 小红打boss#

小红打boss

https://ac.nowcoder.com/acm/contest/65507/E

E. 小红打boss

思路

这题挺难贪心的,为啥这么说,因为有多种思路贪心,但是结果并非最优。

但是无论如何贪心

  • 两种不同属性依次实施
  • 尽量让大的技能伤害double

所以这个贪心,也就变成 最优配对,整体最大化的问题。


来引入一个众数思路

假设 不同属性技能的次数,分别为 a, b, c, 其中c为众数

如果 a + b <= c

分类讨论

  • 如果最大数都在集合c中,那一定可以实现a+b=n-c次
  • 如果最大数也分布于集合a,b中,那a和b直接选取c的最小元素即可, 等价于交换,也一定能实现a+b=n-c次

如果 a + b > c

由众数定理, 一定可以构建 全是不同属性的pair(若n为奇数,单独留一个尾巴),这样可以实现 n/2个最大数的加倍


结合这两个的讨论,可以得出如下的结论

mass = min(n/2, n - max(a, b, c))


代码

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        Map<String, Integer> hash = new HashMap<>();
        hash.put("ice", 0);
        hash.put("fire", 1);
        hash.put("thunder", 2);

        int n = sc.nextInt();
        int[] magic = new int[3];
        int[] attack = new int[n];

        for (int i = 0; i < n; i++) {
            String s = sc.next();
            magic[hash.get(s)]++;
            attack[i] = sc.nextInt();
        }

        Arrays.sort(attack);
        int mass = Math.max(Math.max(magic[0], magic[1]), magic[2]);
        int m = Math.min(n / 2, n - mass);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (i >= n - m) {
                ans += attack[i];
            }
            ans += attack[i];
        }
        System.out.println(ans);

    }

}
全部评论

相关推荐

AI牛可乐:哇塞,恭喜恭喜!48万的年薪,真是让人羡慕呀!看来你找到了一个超棒的工作,可以享受不卷的生活啦!🎉有没有什么求职秘诀想要分享给小牛牛呢?或者,想不想知道我是谁呢?😉(点击我的头像,我们可以私信聊聊哦~)
点赞 评论 收藏
分享
程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客企业服务