简答题
偏难
#7283
田忌赛马 在田忌赛马的故事中,孙膑用自己的下等马对战对手的上等马,自己上等马对阵对手的中等马,自己的中等马对阵对手的下等马,从而赢得了胜利。现在即将进行的是N匹…
田忌赛马
在田忌赛马的故事中,孙膑用自己的下等马对战对手的上等马,自己上等马对阵对手的中等马,自己的中等马对阵对手的下等马,从而赢得了胜利。现在即将进行的是N匹马的赛马比赛。双方队伍的马各分为N等。已知只有当我方马的等级比对方马等级高X等以上(包含X)时,我方才可以取得这场比赛的胜利。如果在N场比赛中我方的胜场数大于对方,则我方取得最终的胜利。现在已知对方这N场比赛的出战方案,请计算所有令我方最终获胜的出战方案。
时间限制:1000
内存限制:65536
输入
第一行两个整数,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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int A[12];
int N, X, xy;
int x[12];
#include <algorithm>
#include <iostream>
using namespace std;
void prt(int arr[], int end) {
int i;
int sum = 0;
for (i = 0; i <= end; i++)
if (arr[i] >= A[i] + X)
sum++;
if (sum >= xy) {
for (i = 0; i <= end; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
}
void perm(int arr[], int len) {
if (len < 2)
return;
int i, j, temp;
do {
// 输出当前序列
prt(arr, len - 1);
i = j = len - 1;
// 向前查找第一个变小的元素
while (i > 0 && arr[i] < arr[i - 1])
--i;
temp = i;
if (i == 0)
break;
// 先后查找第一个比arr[i-1]大的元素
while (temp + 1 < len && arr[temp + 1] > arr[i - 1])
++temp;
swap(arr[i - 1], arr[temp]); // 交换两个值
reverse(arr + i, arr + len); // 逆序
} while (true);
}
int main() {
int i, j, k;
scanf("%d%d", &N, &X);
for (i = 0; i < N; i++)
scanf("%d", &A[i]);
if (N % 2 == 0)
xy = N / 2 + 1;
else
xy = (N + 1) / 2;
for (i = 1; i <= N; i++)
x[i] = i;
perm(x + 1, N);
return 0;
}</pre><p><span> </span><br/></p>
这道题暂未补解析。