HDU1027-Ignatius and the Princess II（全排列问题next_permutation函数的使用）

Ignatius and the Princess II

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14615 Accepted Submission(s): 8391

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

问题描述
现在，我们的英雄找到了BEelzebub feng5166的大门。他打开门，发现feng5166即将杀死我们漂亮的公主。但是现在，魔王必须先击败我们的英雄。 feng5166说：“我有三个问题要问您，如果您能解决，我将释放公主，或者您也将作为我的晚餐。”伊格纳修斯自信地说：“好，最后，我将拯救公主。”

“现在，我将向您展示第一个问题。” feng5166说：“给定一个从1到N的序列，我们定义1,2,3 … N-1，N是所有可以由1到N组成的序列中最小的序列（每个数字可以是并且应该在此问题中仅使用一次。）因此，很容易看到第二个最小的序列是1,2,3 … N，N-1。现在我将给您两个数字N和M。告诉我第M个由1到N组成的最小序列。很容易，不是吗？哈哈哈哈哈……”
您可以帮助Ignatius解决此问题吗？

输入值
输入包含几个测试用例。每个测试用例包含两个数字N和M（1 <= N <= 1000，1 <= M <= 10000）。您可以假设始终有一个序列满足BEelzebub的需求。输入在文件末尾终止。

输出量
对于每个测试用例，只需要输出满足BEelzebub需求的序列即可。输出序列时，应在两个数字之间打印一个空格，但不要在最后一个数字之后输出任何空格。

样本输入
6 4
11 8

样本输出
1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10
题目链接
解题思路：
使用next_permutation()函数循环几次即可，我刚开始定义的是string和char数组，结果想了半天不知道怎么做。突然发现int数组也能使用这个函数（笑），我一直以为只有char数组和string类型能用这个函数…当然这个题可以用深搜写，以后的博客会贴深搜的代码（挖坑），题意就是输入一个数（以6为例），输出第M个字典序（值得注意的是，当把1-n存放在数组里的时候M就是1了，所以循环M-1次就好）。思路当然是把1-n全存数组里面啦，然后循环几次next_permutation()函数就能得到答案啦，注意多组输入，贴AC代码。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		int s[1050];
		int len=0;
		for(int i=1;i<=n;i++)
		  s[len++]=i;
		for(int i=1;i<m;i++)
		  next_permutation(s,s+len);
		for(int i=0;i<len;i++)
		  if(i==0)
		    cout<<s[i];
		  else
		    cout<<" "<<s[i];
		cout<<endl;	  
	}
	return 0;
}