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

    }

}