自动搬运

查看原文

来自洛谷，原作者为

	zhengpie 天降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行指乱其所为，所以动心忍性，曾益其所不能。

搬运于2025-08-24 22:56:51，当前版本为作者最后更新于2024-04-05 20:58:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

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;
}