P3944题解

· · 题解

这里介绍一种和其他题解不太一样的方法，该方法与排序方式有很大关系。

先看题目，题目意思可以概括为以下意思：首先，有三种操作：第一，消耗 1 点法力水晶把敌人攻击小于等于 2 的随从拉过来；第二，耗 4 点法力水晶，把敌人攻击小于等于 3 的随从拉过来；第三，耗 1 点法力水晶，把敌人随从攻击力全部下降 3 点。

首先，大家可能都想得到贪心，由于题目中给定的数据并不保证有序，所以我们要进行排序；看了眼数据范围，五百万算是非常大了，看大家都用得桶排，但其实 sort 吸下氧还是可以过得，这里我采用 sort，具体原因看后面我的方法。

既然是贪心，那么我们就想要看是怎么个贪心法。前面所说的三种操作，我们一个一个看：当这个随从攻击力小于等于 2 时，我们可选择第一和第二种，但显然选第一种更划算；当攻击力小于等于 3 时，此时最优选择显然是第二种，但千万要注意等于 3 时判断下 m 是否已经小于 0 了。

之后，对于拉完所有随从无法击败对手情况，我们可以在输入时就进行这么一个处理：每次输入，判断是否小于 2 的，小于 2 就加这个数本身，否则就按拉过来最大伤害 3 来算，最后输入完成后判断一下，这部分代码：

for(int i=1;i<=n;i++){
     scanf("%d",&a[i]);
     if(a[i]>3){
    fgla+=3;
     }else{
    fgla+=a[i];
     }
}
if(fgla<m){
    printf("Human Cannot Win Dog\n");
}

好，那接下来我们就要开始处理最后第三种操作了，对于一个按从小到大的序列来讲，缩小一些数至指定数，后面需要的缩小药水数只会增加，不会减少，于是，我们由此可判断第三种操作是这几种中最不划算的一种，我们就最后不得不用时才采用它。

你可能以为完了，不！错掉 2 个测试点告诉我们，这玩艺血量是很有可能扣为负的对吧，所以没记错的话就像第二个样例一样，我们每次弄完了就判断下，并返还一些不用，这时，就有一个问题摆在眼前。

问：是拉 3 个 1 攻随从便宜还是一个 3 攻随从便宜？

大家都知道是 3 个 1 攻便宜，那么如果此时恰好超出 3 攻击力，那么我们按贪心来看就该还回 3 攻随从最优，于是我们就在三种操作结束后来进行还回，两个 for，第一个还完大于等于 3 的，第二个还完小于 3 的，切忌：两个 for 不能写在一起，试试就逝世。

最后，代码：

#include<bits/stdc++.h>
using namespace std;
long long int n,m;
const int N=5e6+5;
int a[N];
int fgla=0;
int need=0,number=0;//need缩小药水数,number法力水晶数 
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>3){
            fgla+=3;
        }else{
            fgla+=a[i];
        }
    }
    if(fgla<m){
        printf("Human Cannot Win Dog\n");
    }else{
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){

            a[i]-=3*need;
            if(a[i]<=2){
                number++;
                m-=a[i];
            }else if(a[i]==3){
            if(m<=0){
                break;
            }
                number+=4;
                m-=a[i];
            }else if(a[i]>3){
            if(m<=0){
                break;
            }
                while(a[i]>3){
                    number++;
                    need++;
                    a[i]-=3;
                }
                if(a[i]<=2){
                    number++;
                    m-=a[i];
                }else if(a[i]==3){
                    number+=4;
                    m-=a[i];
                }
            }
        }
        if(m<0){
            int k=0;
            k=k-m;
            for(int j=1;j<=n;j++){
                if(a[j]<=k){
                    if(a[j]==3){
                        number-=4;
                        k-=3;
                    }
                }
            }
            for(int j=1;j<=n;j++){
                if(a[j]<=k){
                    if(a[j]<=2){
                        number--;
                        k-=a[j];
                    }
                }
            }
        }
        printf("%d %d\n",need,number);
    }
    return 0;
}

抄是会被棕名的！