题目大意:
小苯和小红玩卡牌游戏。比较两人当前手牌中的最前一张,对应数字大的那一方得一分并将该张牌从自己的手牌里移除;另一方不得分,手牌也不变。随后进入下一轮。直到两人之中有人没有牌时,游戏结束。求小苯能拿到最高分的排列有多少种。
解题思路:
要使小苯得到高分,就需要让小苯移除的牌数最多,即要将小苯手牌中的大牌放到前面,这样才能在回合里赢下小红。但是什么牌算是大牌呢?根据题目设定,只要小苯目前手里的牌比小红最小的牌数值大,那这张牌一定能够获胜并移除(因为手牌小的不变,小苯先出的比红min大,那么红min一定不会获胜,一直积压在手里)而比红min还要小的牌一定没有机会在回合里获胜,放在最后出,否则会因为牌太小而一直积压在手里浪费后面的大牌。
所以我们可以把小苯的牌分为两类,一类p比红min大,一类q比红min小,两类各进行全排列,相乘即为小苯获得他能拿到的最高分的所有排列数目。
参考代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll p=0,q=0;
vector<ll> a(n),b(n);
for(ll &x:a) cin>>x;
for(ll &x:b) cin>>x;
sort(b.begin(),b.end());
for(ll &x:a){
if(x>b[0])p++;
else q++;
}
ll sum=1;
for(ll int i=1;i<=p;i++){
sum=sum*i%mod;
}
for(ll int i=1;i<=q;i++){
sum=sum*i%mod;
}
cout<<sum<<'\n';
}
return 0;
}



京公网安备 11010502036488号