题解：P10317 [SHUPC 2024] 小A的皇室战争卡组

· · 题解

题目传送门

1.思路

看到题目，很容易想到一种贪心的做法：既然要算有没有做法使得小 A 的平均等级比小 B 的减去 2 要来的大，那么我们直接考虑小 A 的最优平均等级就可以了呀！

于是，在输入的时候，我们只需要保留等级最大的建筑牌，等级前三大的法术牌，等级前七大的部队牌即可。

为什么呢？根据题意，我们知道建筑牌最多可以拿 1 张，那么要使平均等级最大，我们肯定会选自身等级最大的建筑牌啊！同理，我们选等级前三大的法术牌，等级前七大的部队牌。这里特别注意一下部队牌最多可以取 8 - 0 - 1 = 7 张。

2.细节

首先，我们肯定要判断这组卡牌是否合法：

if(c3 < 1 || c1 < 4 || c1 + c2 + c3 < 8)//c1是部队牌个数，c2是建筑牌个数，c3是法术牌个数
{
    cout<<"No"<<endl;continue;
}//如果法术牌的个数小于1，那么就只能取0张法术牌，不合法，直接输出No,另外两个条件也是同理。

然后我们保留保留等级最大的建筑牌，等级前三大的法术牌，等级前七大的部队牌，容易知道，如果所有牌都足够多的话，一共有 6 种取法，记他们为 k_i(i \in [1,6]) 。 于是， k_i 就等于这些东西：

//a1[]为部队牌，a2[]为建筑牌，a3[]为法术牌
int k1 = a1[1] + a1[2] + a1[3] + a1[4] + a2[1] + a3[2] + a3[3] + a3[1];
int k2 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a3[2] + a3[3] + a3[1];
int k3 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a1[6] + a3[2] + a3[1];
int k4 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a3[2] + a2[1] + a3[1];
int k5 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a1[6] + a1[7] + a3[1];
int k6 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a1[6] + a2[1] + a3[1];

然后还要注意到一件重要的事情，就以 k_1 为例。可以发现， k_1 这组卡牌需要用到一张建筑牌，但是注意到，当 c2 < 1 时，无法拿出 1 张建筑牌，于是 k_1 这种情况就不成立。

同理，用下面的代码标记所有不成立的 k_i ：

if(c1 < 7) k5 = -114514;//因为后面与小B的平均等级比较，取最大值，所以把不成立的k[i]设成负数。
if(c1 < 6) k3 = k6 = -114514;
if(c1 < 5) k2 = k4 = -114514;
if(c2 < 1) k1 = k4 = k6 = -114514;
if(c3 < 3) k1 = k2 = -114514;
if(c3 < 2) k3 = k4 = -114514;

然后作比较：

if(max(max(max(k1,k2),max(k6,k5)),max(k3,k4)) / 8 >= (sum / 8 - 2)) cout<<"Yes"<<endl;//sum是小B的卡牌总和
else cout<<"No"<<endl;

当然，类型转换是一件很烦人的事，所以直接比较等级之和就行了。

if(max(max(max(k1,k2),max(k6,k5)),max(k3,k4)) >= (sum - 16)) cout<<"Yes"<<endl;//两边同时乘8
else cout<<"No"<<endl;

3.完整代码

#include<bits/stdc++.h>
using namespace std;
int t,n,a1[114514],a2[114514],a3[114514],b[114514],c[114514];//a1[]为部队牌，a2[]为建筑牌，a3[]为法术牌，b[]为小B的牌
bool cmp(int x,int y)
{
    return x > y;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin>>t;
    for(int bbj = 1;bbj <= t;bbj++)
    {

        cin>>n;
        memset(a1,0,sizeof a1);memset(a2,0,sizeof a2);memset(a3,0,sizeof a3);memset(b,0,sizeof b);memset(c,0,sizeof c);//记得初始化！
        int sum = 0,c1 = 0,c2 = 0,c3 = 0;
        for(int i = 1;i <= n;i++) 
        {
            cin>>c[i];
            if(c[i] == 2) c2++;if(c[i] == 1) c1++;if(c[i] == 3) c3++;
        }
        for(int i = 1,i1 = 1,i2 = 1,i3 = 1;i <= n;i++)
        {
            if(c[i] == 1){cin>>a1[i1];i1++;}
            if(c[i] == 2){cin>>a2[i2];i2++;}
            if(c[i] == 3){cin>>a3[i3];i3++;}
        }
        for(int i = 1;i <= 8;i++) {cin>>b[i];sum += b[i];}
        if(c3 < 1 || c1 < 4 || c1 + c2 + c3 < 8)
        {
            cout<<"No"<<endl;continue;//先特判不合法的
        }
        sort(a1 + 1,a1 + c1 + 1,cmp);//记得排序！
        sort(a2 + 1,a2 + c2 + 1,cmp);
        sort(a3 + 1,a3 + c3 + 1,cmp);
        int k1 = a1[1] + a1[2] + a1[3] + a1[4] + a2[1] + a3[2] + a3[3] + a3[1],k2 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a3[2] + a3[3] + a3[1];
        int k3 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a1[6] + a3[2] + a3[1],k4 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a3[2] + a2[1] + a3[1];
        int k5 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a1[6] + a1[7] + a3[1],k6 = a1[1] + a1[2] + a1[3] + a1[4] + a1[5] + a1[6] + a2[1] + a3[1];
        if(c1 < 7) k5 = -114514;//因为后面与小B的平均等级比较，取最大值，所以把不成立的k[i]设成负数。
        if(c1 < 6) k3 = k6 = -114514;
        if(c1 < 5) k2 = k4 = -114514;
        if(c2 < 1) k1 = k4 = k6 = -114514;
        if(c3 < 3) k1 = k2 = -114514;
        if(c3 < 2) k3 = k4 = -114514;
        if(max(max(max(k1,k2),max(k6,k5)),max(k3,k4)) >= (sum - 16)) 
                cout<<"Yes"<<endl;//两边同时乘8
        else cout<<"No"<<endl;
    }

    return 0;
}