P10072 [GDKOI2024 普及组] 刷野 I

· · 题解

被 Hack 了四次，汗流浃背了。

死亡原因：判断顺序写错了。

贪心题。

我们肯定需要先使用天音波或是天雷破来减少怪物数量，从而使得怪物的数量减少，也就是每轮怪物对 Zayin 造成的伤害减少。

我们首先需要明确，在面对多个怪物时，我们才会使用天雷破。因为当只剩下一个怪物时，天雷破与普通攻击无异，并且会多消耗 1 点能量值。因此只有一个怪物时，我们选择尽量使用天音波，最后当怪物只剩下一滴血时使用普通攻击，节省能量值。

而在剩下两个怪物时，天音波和天雷破都可以使所有怪物的总血量减少两点，但是天音波可以使某一只怪物血量减少得更快。仅当怪物只剩下一滴血时，使用天雷破更优。我们先用天音波攻击血量较少的，这样就可以使得这只怪物对 Zayin 造成的伤害减少。

剩下大于或等于三个怪物时，对比普通攻击某一只怪物，天音波可以使其早一轮死亡，而天雷破可以使所有其他怪物早一轮死亡，天雷破更优。即相较于使用天音波，天雷破可以更多地减少怪物总血量。因此先使用天雷破，直到只剩下两个怪物在按照上文策略攻击。

如果在贪心过程中，能量值消耗完了，则只能使用普通攻击。

更多细节实现请看代码。可以通过目前为止所有 Hack 数据。

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e5+2; 
int a[N];
int b[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    sort(a+1,a+n+1);

    for(int i=1; i<=n; i++){ // 统计同血量怪物，作用见第 67 行 
        int x=i;
        while(1){
            i++;
            if(a[i]!=a[i-1]){
                i--;
                break;
            }
        }
        b[x]=i;
    }

    int bld=0,sum=0; // bld 代表使用天雷破减少的血量，sum 表示总减少血量 
    for(int i=1; i<=n; i++){ // 从血量最少的怪物开始 
        a[i]-=bld;
        if(a[i]<=0) continue;
        if(!m){ // 没有能量只能普通攻击 
            sum+=a[i]*(n-i+1)-1;// 最后此怪物死亡后无法造成伤害，因此减 1 
            continue;
        } 
        bool tyb=false;
        if(n-i+1<3 && !(n-i+1==2 && a[i]==1)){
            long long cnt=0; // 使用天音波的次数 
            while(1){
                if(a[i]==0){ // 怪物死亡 
                    sum+=cnt*(n-i+1)-1;
                    break; 
                } 
                if(m==0){ // 能量耗尽 
                    sum+=(cnt/*天音波*/+a[i]/*剩余血量*/)*(n-i+1)-1; // 对单个怪物，不用像上文一样考虑其它同血量怪物 
                    break;
                }
                if(a[i]==1){
                    if(n-i+1==1) sum+=(cnt+1)*(n-i+1)-1; // 换普通攻击 
                    else sum+=cnt*(n-i+1); // （这里是第 50 行）有多只怪物，还需使用天雷破 
                    break; 
                } 
                m--;a[i]-=2;
                cnt++;tyb=true;
            }
        }
        if(!m) continue; // 没有能量只能普通攻击，以免能量耗尽且怪物剩余一滴血时影响判断 
        if(n-i+1>=3 || (n-i+1==2 && a[i]==1)){ // 还有三个怪物及以上，尽量使用天雷破 
            //有两个怪物且当前怪物血量为 1 时用天雷破更优，见第 50 行 
            long long cnt=0; // 使用天雷破的次数 
            while(1){
                if(a[i]==0){ // 怪物死亡 
                    if(tyb) sum+=cnt*(n-i+1)-1; // 使用过天音波后，原来与此怪物血量相同的现在血量不相同，因此会造成伤害 
                    else sum+=(cnt-1)*(n-i+1)/*用天雷破*/+(n-b[i])/*最后一次其它怪物（与此怪物血量相同的已经死亡，不会造成伤害）*/;//（这里是第 67 行）
                    bld+=cnt;
                    break; 
                } 
                if(m==0){ // 能量耗尽 
                    sum+=cnt*(n-i+1)/*用天雷破*/+(a[i]*(n-i+1)-1)/*普通攻击*/;
                    bld+=cnt;
                    break;
                }
                m--;a[i]--;
                cnt++;
            } 
        }
    }
    cout<<sum;
    return 0;
}