题解 | #初等元素论#

J. 初等元素论

知识点：排序、贪心、枚举、前缀和

先把伤害分为冰火两类，分别从大到小排序。

显然，如果某种元素有 次伤害要打反应，那一定是用伤害最高的 个技能去打。

枚举用火元素触发融化反应的次数 ，反应需要消耗 个火元素技能和 个冰元素技能。假设打完反应还剩 个火元素技能和 个冰元素技能，那么还能进行的冰元素融化反应的次数为 。

排序后使用前缀和可以快速求出前 大的火元素伤害之和，以及前 大的冰元素伤害之和。

关于精度问题：使用64位整数存总伤害的两倍，输出之前除以二并根据奇偶选择小数部分是".0"还是".5"。经过计算发现，直接使用 double 也是可以的，不会有精度丢失。（具体为什么呢？感兴趣的同学可以研究一下 IEEE754 浮点数标准）

标程

C++

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void solve()
{
    int n;
    cin >> n;
    vector<int> cryo, pyro;
    ll ans1 = 0; // ans1 统计基础伤害（两倍）
    for (int i = 0; i < n; ++i)
    {
        char type;
        int damage;
        cin >> type >> damage;
        if (type == 'C')
            cryo.push_back(damage);
        else // type == 'P'
            pyro.push_back(damage);
        ans1 += damage * 2;
    }
    int cryo_count = cryo.size(), pyro_count = pyro.size();

    // 从大到小排序
    sort(cryo.rbegin(), cryo.rend());
    sort(pyro.rbegin(), pyro.rend());
    // 计算 cryo 和 pyro 的前缀和
    vector<ll> cryo_sum(cryo_count + 1), pyro_sum(pyro_count + 1);
    for (int i = 1; i <= cryo_count; ++i)
        cryo_sum[i] = cryo_sum[i - 1] + cryo[i - 1];
    for (int i = 1; i <= pyro_count; ++i)
        pyro_sum[i] = pyro_sum[i - 1] + pyro[i - 1];
    
    ll ans2 = 0; // ans2 统计因元素反应而增加的伤害（两倍）
    const int pyro_melt_max = min(cryo_count, pyro_count); // 火打冰导致的融化反应次数上限
    for (int pyro_melt = 0; pyro_melt <= pyro_melt_max; ++pyro_melt) // 枚举火打冰导致的融化反应次数
    {
        ll pyro_melt_damage = pyro_sum[pyro_melt] * 2; // 火打冰导致的融化反应伤害（两倍）
        int cryo_melt = min(cryo_count - pyro_melt, (pyro_count - pyro_melt) * 2); // 冰打火导致的融化反应次数
        ll cryo_melt_damage = cryo_sum[cryo_melt]; // 冰打火导致的融化反应伤害（两倍）
        ans2 = max(ans2, pyro_melt_damage + cryo_melt_damage);
    }
    ll ans = ans1 + ans2; // 总伤害（两倍）
    cout << (ans / 2) << (ans % 2 == 0 ? ".0" : ".5") << '\n'; // 输出答案（保留一位小数）
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Java

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

public class Main {
    static Kattio io = new Kattio();

    static void solve() {
        int n = io.nextInt();
        long ans1 = 0;
        int[] cryo = new int[n];
        int[] pyro = new int[n];
        int cryo_count = 0, pyro_count = 0;
        for (int i = 0; i < n; ++i)
        {
            String type = io.next();
            int damage = io.nextInt();
            if (type.equals("C"))
            {
                cryo[cryo_count++] = damage;
            }
            else
            {
                pyro[pyro_count++] = damage;
            }
            ans1 += damage * 2;
        }
        // 出题人不会写 Java，只会用这种笨办法降序排序。
        // 如果有什么高论，欢迎在评论区指出。
        cryo = Arrays.copyOf(cryo, cryo_count);
        cryo = Arrays.stream(cryo)
            .boxed()
            .sorted((a, b) -> b - a)
            .mapToInt(Integer::intValue)
            .toArray();
        pyro = Arrays.copyOf(pyro, pyro_count);
        pyro = Arrays.stream(pyro)
            .boxed()
            .sorted((a, b) -> b - a)
            .mapToInt(Integer::intValue)
            .toArray();

        long cryo_sum[] = new long[cryo_count + 1];
        long pyro_sum[] = new long[pyro_count + 1];
        for (int i = 1; i <= cryo_count; ++i)
        {
            cryo_sum[i] = cryo_sum[i - 1] + cryo[i - 1];
        }
        for (int i = 1; i <= pyro_count; ++i)
        {
            pyro_sum[i] = pyro_sum[i - 1] + pyro[i - 1];
        }

        long ans2 = 0;
        final int pyro_melt_max = Math.min(cryo_count, pyro_count);
        for (int pyro_melt = 0; pyro_melt <= pyro_melt_max; ++pyro_melt)
        {
            long pyro_melt_damage = pyro_sum[pyro_melt] * 2;
            int cryo_melt = Math.min(cryo_count - pyro_melt, (pyro_count - pyro_melt) * 2);
            long cryo_melt_damage = cryo_sum[cryo_melt];
            ans2 = Math.max(ans2, pyro_melt_damage + cryo_melt_damage);
        }
        long ans = ans1 + ans2;
        io.printf("%d%s\n", ans / 2, ans % 2 == 0 ? ".0" : ".5");
    }

    public static void main(String[] args) {
        int T = io.nextInt();
        while (T-- > 0) {
            solve();
        }

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

def solve():
    n = int(input())
    cryo = []
    pyro = []
    ans1 = 0
    for _ in range(n):
        element, damage = input().split()
        damage = int(damage)
        if element == "C":
            cryo.append(damage)
        else:
            pyro.append(damage)
        ans1 += damage * 2
    cryo.sort(reverse=True)
    pyro.sort(reverse=True)
    cryo_sum = [0]
    pyro_sum = [0]
    for i, damage in enumerate(cryo):
        cryo_sum.append(cryo_sum[-1] + damage)
    for i, damage in enumerate(pyro):
        pyro_sum.append(pyro_sum[-1] + damage)
    ans2 = 0
    pyro_melt_max = min(len(cryo), len(pyro))
    for pyro_melt in range(pyro_melt_max + 1):
        pyro_melt_damage = pyro_sum[pyro_melt] * 2
        cryo_melt = min(len(cryo) - pyro_melt, (len(pyro) - pyro_melt) * 2)
        cryo_melt_damage = cryo_sum[cryo_melt]
        ans2 = max(ans2, pyro_melt_damage + cryo_melt_damage)
    ans = ans1 + ans2
    print("{}.{}".format(ans // 2, "5" if ans % 2 == 1 else "0"))


T = int(input())
for _ in range(T):
    solve()