题解 | #Card Game#

本题是牛客寒假竞赛训练营的第二题

题目链接链接：https://ac.nowcoder.com/acm/contest/120561/B

题目大意： 小苯和小红俩个人做游戏，每个人分到手n个卡牌，然后比较大小，拿出大的卡牌的人加一分，另一人不得分，同时这个大的卡牌要从本轮获胜的那个人手中移除，游戏结束的标准就是哪一方卡牌变为零就结束。

题目要求： 现在这个小苯想要得到尽可能多的分数，让我们求出当小苯得到最多分数时有多少种排法。

题目分析： 初步来看这是一个在高中就出现过的排列问题，这时候我们就要想，只有当小苯的卡牌被尽可能的移除时小笨才能得到更多的分数，所以我们就要找小红卡牌中的软柿子捏，即小红卡牌中最小的那个数，找到小苯卡牌中大于小红卡牌中最小的那个卡牌的个数，让小苯卡牌中的数被尽可能消耗，若小红卡牌中最小的那个数被提前删掉，那么小苯手中的卡牌就变得更难以删掉。所以要先找到小红卡牌中最小的那个数：

ll mi=1e9;
	for(int i=1;i<=n;i++){
		cin>>b[i];
		if(b[i]<mi){
			mi=b[i];
		}
	}

此时找到最小的数就是mi，然后再找到小苯卡牌中大于mi的数的个数：

ll cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>mi){
			cnt++;
		}
	}

然后大于mi的数就有cnt！种排法，小与mi的数就有（n-cnt）！种排法，最后将它们相乘，就得到最终答案：

ll ans=1;
	for(int i=1;i<=cnt;i++){
		ans=(ans*i)%mod;
	}
	for(int i=1;i<=n-cnt;i++){
		ans=(ans*i)%mod;
	}

最后看一下整体代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
ll a[N],b[N];
const int mod=998244353;
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll mi=1e9;
	for(int i=1;i<=n;i++){
		cin>>b[i];
		if(b[i]<mi){
			mi=b[i];
		}
	}
	ll cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>mi){
			cnt++;
		}
	}
	ll ans=1;
	for(int i=1;i<=cnt;i++){
		ans=(ans*i)%mod;
	}
	for(int i=1;i<=n-cnt;i++){
		ans=(ans*i)%mod;
	}
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	}
}