题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字：

三进制数

123

132

213

231

312

321

代表的数字

1

2

3

4

5

6

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入描述:

第一行有一个正整数N，表示火星人手指的数目。
第二行是一个正整数M，表示要加上去的小整数。
下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出描述:

输出只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

示例1

输入

5
3
1 2 3 4 5

输出

1 2 4 5 3

解答

刚开始看到这个题目，还是有点懵逼的，但是知道它是一个全排列问题，所以赶紧的去了解了一下全排列，顺利地解决了这个问题。

本题就是要求求出经过M次排列后的结果。

对于一系列的数，比如这个数组，要想对它进行全排列，要经过以下几个步骤：

1.判断该数组能不能进行全排列
对于一个数组来说，如果他为num[5] = {5,4,3,2,1},那么也就没有必要再去全排列了，因为他已经是最大的数字了，没有后继。所以，想要判断一系列数能不能进行全排列，判断他有没有后继（即这个数是否存在非递减的两个数），如果有（存在），那就可以进行排列。
判断是否能进行全排列的代码： 

bool hasNext()
{
    for( int i = N; i > 0; i--)
        if( num[i] > num[i-1])
            return true;
    return false;
}


2.如何进行全排列（当时想这个想了挺久的==）
在确定这一系列的数有后继之后，那如何去找到它的后继呢？要明确，一个数的后继要满足两个条件：比这个数大、在比这个数大的数里面最小。
首先，我们从右往左遍历这个数组，找出一个数，满足,然后用top将这个ii记录下来（即top为极大值点），并且确定了一个要交换的数；
接着，我们要确定第二个要交换的数， 而第二个要交换的数为中最小的数并且这个数要大于第一个被交换的数；
然后，交换两个数；
最后，如果交换之后，及其后面的数如果还是单调递减的，那就将其位置对调，得到最小的。
找出极大值得top并记录
for( int i = N-1; i >0; i--)
    {
        if( num[i] > num[i-1])
        {
            top = i;
            break;
        }
    }
确定第二个要交换的数
int mm = top;//mm为要交换数的下标
    //如果top后面还有比top前面的数(也就是num[top-1)小的话，就先交换那个小的数
    for( int i = top; i < N; i++)
    {
        if( num[i] > num[top-1] && num[i] < num[top])
            mm = i;
    }
交换两个数
void _swap( int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
_swap(&num[mm],&num[top-1]);
得到最小
for(int i=0;i<=(top+N-1)/2-top;i++)
        _swap(&num[i+top],&num[N-1-i]);
大概的思路就是这个样子了==
可能讲的还不是太清楚，其实对于全排列问题，用递归、c++的库函数都可以完成的。
源码： 
#include<cstdio>
  
using namespace std;
const int maxn = 10000+5;
int num[maxn];
int N,M;
  
//个人觉得这个不写也没问题，但是为了安全，还是写着吧
int hasNext()
{
    for( int i = N-1; i > 0; i--)
        if( num[i] > num[i-1])
            return true;
    return false;
}
  
void _swap( int *a, int *b)
{
    int m = *a;
    *a = *b;
    *b = m;
}
  
void next()
{
    int top;
    //从又开始遍历数组，找出右边第一个极大值，用top保存(此时也找到了第一个要交换的数num[top-1])
    for( int i = N-1; i > 0; i--)
       if( num[i] > num[i-1])
       {
           top = i;
           break;
       }
  
    //找出第二个要交换的数
    int mm = top;
    for( int i = top; i < N; i++)
    {
        if( num[i] > num[top-1] && num[i] < num[top])
            mm = i;
    }
  
    _swap( &num[top-1], &num[mm]);
  
    for( int i = 0; i <= (top+N-1)/2-top; i++)
        _swap( &num[i+top], &num[N-1-i]);
  
}
  
int main()
{
    while( scanf("%d%d",&N,&M) == 2)
    {
  
        for( int i = 0; i < N; i++)
            scanf("%d",&num[i]);
  
        for( int i = 0; i < M; i++)
        {
            if( hasNext())
                next();
        }
  
        printf("%d",num[0]);
        for( int i = 1; i < N; i++)
            printf(" %d",num[i]);
        printf("\n");
  
    }
  
    return 0;
}
//用vector容器不用数组更容易实现呢==

用c++中的库函数 
#include<cstdio>
#include<algorithm>
  
using namespace std;
const int maxn = 10000+5;
int num[maxn];
  
int main()
{
    int n,m;
    while( scanf("%d%d",&n,&m) == 2)
    {
        for( int i = 0; i < n; i++)
            scanf("%d",&num[i]);
  
        for( int i = 0; i < m; i++)
            next_permutation(num,num+n);
  
        for( int i = 0; i < n; i++)
            printf(i==n-1?"%d\n":"%d ",num[i]);
  
    }
  
    return 0;
}



来源：Vmorish