贪心-肮脏的牧师

goto

思路

可以明确的是，先从小到大枚举出缩小卡片的数量
可以发现，卡片2的性价比最高，1其次，3最差，所以分别统计出可以使用的123号卡片的数量，然后先后使用213号卡片，需要注意的是，如果3号使用后敌方的hp<0，说明前面的1或2号卡片可以少用几张，贪心的策略也就出来了

代码

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

int n,m,x,mt,f[30005],cnt[4];

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        scanf("%d",&x);
        mt=max(mt,x);
        f[x]++;
    }
    for (int i=0;i<=mt/3;++i){
        for (int j=1;j<=3;++j){
            cnt[j]+=f[i*3+j];
        }
        int tm=m,A=i;
        if (tm>0){
            int need=min(cnt[2],tm/2+(tm%2!=0));
            tm-=need*2;
            A+=need;
        }
        if (tm>0){
            int need=min(cnt[1],tm);
            tm-=need;
            A+=need;
        }
        if (tm>0){
            int need=min(cnt[3],tm/3+(tm%3!=0));
            tm-=need*3;
            A+=4*need;
            if (tm==-2){  //如果多用了2
                if (cnt[1]>=2){ //优先撤销2张1号卡
                    A-=2;
                }else if (cnt[2]>=1){
                    A--;
                }
            }else if (tm==-1){ //如果多用了1
                if (cnt[1]>=1){
                    A--;
                }
            }
        }
        if (tm<=0){
            cout<<i<<' '<<A<<endl;
            m=tm;
            break;
        }
    }
    if (m>0){
        puts("Human Cannot Win Dog");
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/103/