CF1784A Monsters (easy version) 题解

年代久远

您正在查看一篇年代久远的题解，由于 Markdown 格式不兼容等问题，页面渲染可能会出现问题。其中的时效性信息可能不再有效，请仔细辨别。

思路

我们肯定希望技能 2 用在最划算的地方，也就是使用一次技能 2 「杀死」更多的怪物，直接结束游戏 ~~（毕竟这么牛波一的技能每局只能用一次）。~~

如何保证使用技能 2 能秒杀全场呢？

很简单，只要保证血量序列里有若干血量为 \(1\) 的怪物，有若干血量为 \(2\) 的怪物，还有 \(3,\ 4,\ 5,\ ...\)，这样每扣一次血必定有至少一只怪物被「杀死」，技能继续扣血，还有至少一只怪物被「杀死」，技能继续，循环到结束游戏。经过若干次技能 1 之后，怪物血量序列排序后如下：

\[\overbrace{1,\ ...}^{\texttt{若干个}1},\ \overbrace{2,\ ...}^{\texttt{若干个}2},\ \overbrace{3,\ ...}^{\texttt{若干个}3},\ \overbrace{4,\ ...}^{\texttt{若干个}4},\ ...\]

简单地来说，我们只需要使用技能 1 直到怪物血量满足：

排序后相邻血量相差不超过 \(1\)。

就行了。

代码

代码也很好写啦，排序一遍检查相邻血量之差有没有大于 \(1\) 的，给它降下来。

// Coder          : Hellolin
// Time           : 2023-02-06 10:25:33
// Problem        : Monsters (easy version)
// Contest        : Luogu
// URL            : https://www.luogu.com.cn/problem/CF1784A
// Time Limit     : 4000 ms
// Memory Limit   : 500 MiB

#include <iostream>
#include <algorithm>

#define ll long long
const int MAX = 200205;

int t;
ll n, a[MAX], ans; // 记得开 long long
int main()
{
    // 加速输入输出
    std::ios::sync_with_stdio(false);

    // 多组测试数据
    std::cin>>t;
    while(t--)
    {
        std::cin>>n;
        for (int i=1; i<=n; i++) std::cin>>a[i];

        // 排序
        std::sort(a+1, a+1+n);

        // 计算答案，输出，记得 ans=0
        ans=0;
        for (int i=1; i<=n; i++) // 注意这里 i 要从 1 开始，万一怪物序列里没有 1 需要弄出来一个 1
        {
            if (a[i]-a[i-1]>1) // 相邻的两个血量相差大于 1
            {
                ans += a[i]-a[i-1]-1; // 需要使用技能 1
                a[i] = a[i-1]+1;
            }
        }
        std::cout<<ans<<std::endl;
    }

    return 0;
}

CF1784A Monsters (easy version) 题解

思路

代码

评论