个人感觉这个函数是值得学习一下的,全排列专用,用于将当前数组换到下一个排列 高效避免了自己手动写轮子去模拟全排列! 当前有两个队伍进行PK,每次各选出一个人PK,能力值大的获胜,最终比较获胜的总局数,求队伍一获胜,失败,平的可能。 队伍一不动,对队伍二进行全排列,进行PK统计局数即可next_permutation
举个栗子:
b[] = 1 2 3 4 5
next_pertutation(b,b+5)
b[] = 1 2 3 5 4
不过值得注意的是,这个函数返回的是当前排列的下一个,如果存在则返回true,否则返回false
所以如果我们需要枚举全排列时,一定记得要对其先sort后再用next_permutation
例题:
题目大意:
解题思路:
不过值得注意的是,因为存在能力值相同的人,所以为了区别开这种情况,所以对B需要取pair<能力值,位置>以分辨代码实现:
# include<bits/stdc++.h>
using namespace std;
const int N = 11;
int a[N];
pair<int,int>b[N];
int main(){
int n;
cin>>n;
for(int i = 1;i <= n;++i) cin>>a[i];
for(int i = 1;i <= n;++i) cin>>b[i].first,b[i].second = i;
int c1 = 0,c2 = 0,c3 = 0;
sort(b+1,b+1+n);
do{
int t1 = 0,t2 = 0;
for(int i = 1;i <= n;++i){
t1 += a[i]>b[i].first;
t2 += a[i]<b[i].first;
}
if(t1 == t2) c3++;
else if(t1<t2)c2++;
else c1++;
}while(next_permutation(b+1,b+1+n));
cout<<c1<<" "<<c2<<" "<<c3<<endl;
return 0;
}