[GDKOI2024 普及组] 刷野 I 题解

i_was_wrong · 2024-01-21 09:27:55 · 题解

[GDKOI2024 普及组] 刷野 I 题解

感谢潘德理2010提供的hack。

选择使用贪心的思想，通过不断选择最优的攻击方式来最小化受到的血量伤害。

思路

一眼贪心：

1. 当我们还有能量且怪兽剩余数量大于 2，那我们就用天雷破。

2. 但我们还有能量且怪兽数量小于等于 2，若有怪兽血量等于 1，使 用天雷破。如果没有，使用天音波。

3. 没有能量了，用普通攻击。

证明

我们想要让每次怪物受到的总伤害最大。那么当怪物数量大于 2 时，显然使用天雷破所造成的伤害更多。当怪物数量小于等于 2 且有一只怪血量为 1 是使用天雷破还可以击败一只怪更加划算。其余使用天音波即可。

代码

include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5 + 5;

int n, m, a[N], ans, q;  // 定义全局变量：怪物数量n，能量值m，怪物血量数组a，最终答案ans，额外伤害q

// 模拟游戏战斗的函数
void play() {
    int x = a[n - 1], y = a[n];
    while (x > 0 || y > 0) {
        if (m > 0) {
            m--;
            if (x > 2)
                x -= 2, ans += 2;
            else if (x == 2)
                x -= 2, ans++;
            else if (x == 1 && y > 1)
                x--, y--, ans++;
            else if (x == 1 && y == 1)
                x--, y--;
            else if (y == 2)
                y -= 2;
            else
                y -= 2, ans++;
        } else {
            if (x > 0) {
                ans += 2 * (x - 1) + y;
                x = 0, y = 0;
            } else if (y > 0) {
                ans += y - 1;
                y = 0;
            }
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    if(a[n]==1){cout<<0;return 0;}//注意，这里要特判，是否可以天音波直接带走
    if (a[n - 2] <= m) {
        // 特殊情况处理：攻击第n-2个怪物，然后进行普通攻击
        m -= a[n - 2];
        for (int i = 1; i <= n - 2; i++) ans += a[i] - 1;
        ans += 2 * a[n - 2];
        a[n - 1] -= a[n - 2], a[n] -= a[n - 2];
        play();
    } else {
        // 一般情况处理：贪心算法计算受到的总伤害
        for (int i = 1; i <= n; i++) {
            ans += q;
            ans += a[i] - 1;
            if (a[i] >= m) q += a[i] - m;
        }
    }

    cout << ans;  // 输出最终答案
    return 0;
}