hdu 1027 水+模拟排列

谁借莪１个温暖的怀抱￠ 2022-08-08 14:51 169阅读 0赞

题意：

给定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;
    }