首页 > 试题广场 >

#include using namespa...

[填空题]
#include <cstdio>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall( ) {
    for (int i = 1; i <= n; ++i)
        if (a[i] != b[i]) return a[i] < b[i];
    return false;
}
bool getPermutation(int pos) {
    if (pos > n) {
        return isSmall( );
    }
    for (int i = 1; i <= n; ++i) {
        if (!isUse[i]) {
            b[pos] = i; isUse[i] = true;
            if (getPermutation(pos + 1)) {
                return true;
            }
            isUse[i] = false;
        }
    }
    return false;
}
void getNext( ) {
    for (int i = 1; i <= n; ++i) {
        isUse[i] = false;
    }
    getPermutation(1);
    for (int i = 1; i <= n; ++i) {
                a[i] = b[i];
    }
}
int main ( ) {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= t; ++i) {
        getNext( );
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d", a[i]);
        if (i == n) putchar('\n'); else putchar(' ');
    }
    return 0;
}

输入1:6 10 1 6 4 5 3 2
输出1:1(3 分)
输入2:6 200 1 5 3 4 2 6
输出2:2(5 分)

首先, getNext()ext_permutation(a + 1, a + n + 1)

括号(1)比较简单

执行 getNext() 的次数 : 序列结果
0 : 2 1 3 5 6 4
1 : 1 6 5 2 3 4
2 : 1 6 5 2 4 3
3 : 1 6 5 3 2 4
4 : 1 6 5 3 4 2
5 : 1 6 5 4 2 3
6 : 1 6 5 4 3 2
7 : 2 1 3 4 5 6
8 : 2 1 3 4 6 5
9 : 2 1 3 5 4 6
10 : 2 1 3 5 6 4

第(2)小题需要数学

start : 1 5 3 4 2 6
     => 1 5 3 6 4 2 (末尾 2 位从大到小) cost = 3
     => 1 5 6 4 3 2 (末尾 4 位从大到小) cost = 3 + 12 = 15
     => 1 6 5 4 3 2 (末尾 5 位从大到小) cost = 15 + 4! = 39
     => 2 1 3 4 5 6 (首位为 2, 末尾 5 位从小到大) cost = 39 + 1 = 40
     => 3 1 2 4 5 6 (首位为 3, 末尾 5 位从小到大) cost = 40 + 5! = 160
     => 3 2 1 4 5 6 (开头为 3 2, 末尾 4 位从小到大) cost = 160 + 4! = 184
     => 3 2 5 1 4 6 (开头为 3 2 5, 末尾 3 位从小到大) cost = 184 + 2 * 3! = 196 (这里的 "2*" : 1 => 4 => 5, 5 是 "1 4 5 6" 中第 3 大的数, 3 - 1 = 2)
     => 3 2 5 6 1 4 (答案) cost = 196 + 4 = 200 (简单枚举)
发表于 2019-09-07 20:13:21 回复(0)