A40410. 田忌赛马在田忌赛马的故事中，孙膑用自己的下等马对战对手的上等马，自己上等马对阵对手的中等马，自己的中等马对阵对手的下等马，从而赢得了胜利。现在即将进行的是N匹马的赛马比赛。双方队伍的马各分为N等。已知只有当我方马的等级比对方马等级高X等以上（包含X）时，我方才可以取得这场比赛的胜利。如果在N场比赛中我方的胜场数大于对方，则我方取得最终的胜利。现在已知对方这N场比赛的出战方案，请计算所有令我方最终…
填空题
中等
知识点
题目描述
田忌赛马
在田忌赛马的故事中，孙膑用自己的下等马对战对手的上等马，自己上等马对阵对手的中等马，自己的中等马对阵对手的下等马，从而赢得了胜利。现在即将进行的是N匹马的赛马比赛。双方队伍的马各分为N等。已知只有当我方马的等级比对方马等级高X等以上（包含X）时，我方才可以取得这场比赛的胜利。如果在N场比赛中我方的胜场数大于对方，则我方取得最终的胜利。现在已知对方这N场比赛的出战方案，
请计算所有令我方最终获胜的出战方案。
输入
第一行两个整数，N和X。N≤9, 0 ≤ X < N。 第二行N个正整数，A(1)…A(N)。A(i)表示第i场比赛对方
马的等级，1≤i≤N。等级越高越强
输出
按字典序输出所有我方最终获胜的方案，每个方案一行。每行是N个正整数，第i个数表示我方第i场比赛马的等级。
样例输入
样例1输入
3 1
3 2 1
样例2输入
3 0
3 1 2
样例输出
样例1输出
1 3 2
样例2输出
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
参考答案
#include<bits/stdc++.h>
using namespace std;
int n,x;
int a[15];//对方
bool b[15];//我方可用马匹
int c[15];//我方出场顺序
void dfs(int step){
if(step>n){//如果都安排完了
int w=0;//赢得场数
for(int i=1;i<=n;i++){
if(c[i]-a[i]>=x){//赢了
w++;
}
}
if(w>n/2){//赢超过一半
for(int i=1;i<=n;i++){
cout<<c[i]<<" ";//输出
}
cout<<endl;//空格
}
return;
}
for(int i=1;i<=n;i++){//循环按字典序安排马匹
if(b[i]==0){
b[i]=1;
c[step]=i;
dfs(step+1);
b[i]=0;
}
}
}
int main(){
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(1);//深搜
system("color 6");//按个人喜好调换颜色或删除
return 0;
}
上一题
下一题