hdu1027

     我做这个题真的很久，但用自己的方法还是没做出来，只能借用别人的方法，别人的方法也看了几个小时才看懂，接下来进入正题。

Problem Description

Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, "I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too." Ignatius says confidently, "OK, at last, I will save the Princess."

"Now I will show you the first problem." feng5166 says, "Given a sequence of number 1 to N, we define that 1,2,3...N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it's easy to see the second smallest sequence is 1,2,3...N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It's easy, isn't is? Hahahahaha......"
Can you help Ignatius to solve this problem?

 

Input

The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub's demand. The input is terminated by the end of file.

 

Output

For each test case, you only have to output the sequence satisfied the BEelzebub's demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.

 

Sample Input

6 4 11 8

 

Sample Output

1 2 3 5 6 4 1 2 3 4 5 6 7 9 8 11 10

 

Author

Ignatius.L

 

Recommend

首先把题看懂，这个题有个巧点，虽然n<=1000, 但m<=10000,所以n

只算前8个就满足题意, 直接上代码，会详解；

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int biao[9]= {1,1,2,6,24,120,720,5040,40320};//这一步是把8个节点拿出来，待会好比较，这个要求出来下面有代码
int main()
{
    int n,m,x,a,cnt,i;
    int rest[2],store[9];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i = 0; i < 9; i++)
            store[i] = 1005;//建立的新数组，全为1005

        for(i = 1; i <= 8; i++)
            if(biao[i] > m)//比较m在哪个位置，用x来记录
            {
                x = i;
                break;
            }
        for(i = 1; i <= n - x; i++)
            printf("%d ",i);//将前面的无影响数字打出来
        for(i = 1; i <= x; i++)
            store[i] = n - x + i;//将后面要排序的数字放在store[]的前几个元素，通常是x个后面数字n,n-1,n-2......;
        for(i = x - 1; i >= 1; i--)
        {
            sort(store, store + 9);//对里面的数字进行排序，所有1005被放在后面
            a = m / biao[i];//核心：判断m中有几个biao[i],用来判断这个位置该放第几大的数字
            m %= biao[i];//将m取余，好用做下一判断是第几大数字
			if(m)//最后m等于0，或1；
            {
                printf("%d ",store[a]);
                store[a] = 1005;
            }
            else//这一步是m==0时，m是阶乘的倍数
            {
                printf("%d ",store[a - 1]);
                store[a - 1] = 1005;
                break;
            }
        }
        sort(store, store + 9);//这几步很重要，是为了防止break后，后面的数字还没打上去，添上剩下的数字
        for(i = 8; i > 0; i--)
            if(store[i] != 1005)
            printf("%d ",store[i]);
        printf("%d\n",store[0]);//格式问题
    }
	return 0;
}//注意体会，最好在纸上演算一遍

int stratum(int x)
{
    if(x==1)return 1;
    else
        return stratum(x-1)*x;
}//阶乘函数

int sort(int a[])
{
    int i,j,k,t;
    for(i=0;i<9;i++)
    {
        k=i;
        for(j=i+1;j<9;j++)
            if(a[k]>a[j])k=j;
        t=a[k];
        a[k]=a[j];
        a[j]=t;
    }
    return 0;
}//c语言sort