简答题
偏难
#7066
田忌赛马 在田忌赛马的故事中,孙膑用自己的下等马对战对手的上等马,自己上等马对阵对手的中等马,自己的中等马对阵对手的下等马,从而赢得了胜利。现在即将进行的是N匹…
田忌赛马
在田忌赛马的故事中,孙膑用自己的下等马对战对手的上等马,自己上等马对阵对手的中等马,自己的中等马对阵对手的下等马,从而赢得了胜利。现在即将进行的是N匹马的赛马比赛。双方队伍的马各分为N等。已知只有当我方马的等级比对方马等级高 X 等以上(包含 X )时,我方才可以取得这场比赛的胜利。如果在N场比赛中我方的胜场数大于对方,则我方取得最终的胜利。现在已知对方这 N 场比赛的出战方案,请计算所有令我方最终获胜的出战方案。
时间限制:1000
内存限制:65536
输入
第一行两个整数, N 和 X 。0≤X<N≤9 。 第二行 N 个正整数,A1, A2,..., AN 。Ai表示第 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>
这道题暂未补解析。