hdu 1027 水+模拟排列-蒲公英云

hdu 1027 水+模拟排列

题意：

    给定1~n的序列，求第m小的序列。大小比较按照字符串比较的顺序。

分析：

   n个数有n！个排列方式，如果在n里面取出最小的1，那么后面的就有n-1！个序列，按照这个原理，从前往后推，可以得出最后的序列。

代码：

#include <iostream>
#include <cstring>
using namespace std;
int ans[1001],n;
bool f[1001];
int calJc(int k) {
    int i , s = 1;
    for (i = 1; i <= k; i++)
        s = s * i;
    return s;
}
void tmj(int k, int m) {
    int i, tt, p;
    if (k > 0) {
    int s = calJc(k - 1);
    int t = m / s;
    if (m % s != 0) t++;
    tt = t;
    for (i = 1; i <= n; i++)
    if (f[i] == 0) {
        t--;
        if (t == 0) {
                ans[n - k + 1] = i;
                f[i] = 1;
                break;
        }
    }
    tmj(k - 1, m - (tt - 1) * s);
    } else if (m == 0) {
        p = n - k + 1;
        for (i = 1; i <= n; i++)
        if (f[i] == 0) {
                ans[p] = i;
                p++;
        }
    }
}
int main() {
    int s, i, m;
    while (cin >> n >> m) {
        int ii = 1;
        int s = 1;
        memset(f, 0, sizeof(f));
        while (s < m) {
            ii++;
            s = s * ii;
        }
        for (i = 1; i <= n - ii; i++) {
            f[i] = 1;
            ans[i] = i;
        }
        //确定n-i+1个数的情况下，第一个数是什么
        tmj(n - i + 1, m);
        //Out
        for (i = 1; i < n; i++)
            cout << ans[i] << ' ';
        cout << ans[n] << endl;
    }
    return 0;
}