#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,a[100001];
main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)next_permutation(a,a+n+1);
for(int i=1;i<=n;i++)printf("%d ",a[i]);
}

//离散书上的经典算法，《离散数学及其应用》P436
#include <iostream>
#include <algorithm>
 using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    int arr[10005];
    int N, M;
    int j, k, r, s;
    cin >> N >> M;
    for(int i = 0; i < N; i++)
        cin >> arr[i];
    while(M--)
    {
        j = N - 2;
        while(arr[j] > arr[j+1])
            j--;
        k = N - 1;
        while(arr[k] < arr[j])
            k--;
        swap(arr[k], arr[j]);
        r = N - 1;
        s = j + 1;
        while(r > s)
        {
            swap(arr[s], arr[r]);
            r--; s++;
        }
    }
    for(int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

next_permutation这也能叫题解吗？

因为总数很大，使用DFS去求接下来第N个显然会超时，所以这是个数学问题

首先A个数进行全排列总共有A!种方式。
因此，进行递归操作，对于倒数第N-1位数，其之后应该有N个数，如果进行全排列就有N!个可能性。
但如果要让第N-1个数变化。首先因为后N个数是中间一部分的排列，需要先取K次，使得N-1位数进行第一次变化，之后每变化一次，则需要增加N!个数，总计变化P次，当然，最后一次可能并不够N!个，剩下的部分T就是后N个数的第T个全排列。

也就是说将输入M分解为 K＋P * N! + T，算出各个值即可

问题的思路大致如此。

next_permuration!
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<bitset>
#include<algorithm>
#include<string>
#include<cstring>
#include<deque>
#include<ctime>
#include<queue>
#define mp make_pair
using namespace std;
inline long long stoi(string s){
long long rt=0;
for(int i=0;i<s.size();i++) rt=rt*10+s[i]-'0';
return rt;
}
inline string itos(long long x){
string rt="";
while(x){
rt+=(char)(x%10+'0');
x/=10;
}
reverse(rt.begin(),rt.end());
return rt;
}
const int INF=1000000009;
int a[10005],n,m;
int main(){
cin>>n>>m;
int i,j;
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<m;i++) next_permutation(a,a+n);
for(i=0;i<n;i++) cout<<a[i]<<' ';
return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=10000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

int n,m;
int a[N];
void next(int a[]) {
    int pos=1;
    REP(i,2,n) if (a[i]>a[i-1]) pos=i;
    if (pos==1) return;
    int pos2=0;
    REP(i,pos,n) {
        if (a[i]>a[pos-1]&&(pos2==0||a[i]<a[pos2])) {
            pos2=i;
        }
    }
    swap(a[pos2],a[pos-1]);
    sort(a+pos,a+1+n);
    /*
    FOR(i,n) cout<<a[i]<<" ";
    cout<<endl;
    */
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,n) cin>>a[i];
    while (m--) next(a);
    FOR(i,n) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

#include<cstdio>
#include<algorithm>
int a[10010];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    while(m--) std::next_permutation(a+1, a+n+1);
    for(int i=1; i<n; i++) printf("%d ", a[i]);
    printf("%d", a[n]);
    return 0;
}

！刷题并不重要，重要的是理解！
祝大家 RP+++

#include <iostream>
#include <algorithm>
using namespace std;
int a[10005],
    n,m;
int main()
{
    ios::sync_with_stdio(false); //iostream 加速开关
    cin >> n >> m; //INPUT
    for(int i=0; i<n; i++)
        cin >> a[i];
    for(; m--;) // 循环m次
        next_permutation(a,a+n); // C++STL 下一个排列
    for(int i=0; i<n; i++) // OUTPUT
        cout << a[i] << ' ';
    cout << endl;
}

直接调用STL就好啦~
当然要认真地写常规算法也是可以的

#include <iostream> 
#include <algorithm>
using namespace std; 
int n,m,martian[10001]; 

void print()  
{
  for(int i=0;i<n-1;i++) 
    cout<<martian[i]<<' '; 
  cout<<martian[n-1]<<"\n";   
}

int main()   
{   
  cin>>n>>m;
  for(int i=0;i<n;i++)
    cin>>martian[i];
  for(int i=1;i<=m;i++)
    next_permutation(martian,martian+n);     
  print();
  return 0; 
}

var
n,k,i,ans:longint;
a:array[1..10000] of longint;

procedure qsort(l,r:longint);
var
i,j,mid,t:longint;
begin
i:=l;
j:=r;
mid:=a[(l+r) div 2];
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

procedure try(p:longint);
var
i,k,l,j,t:longint;
t1:boolean;
begin
if ans=0 then
begin
for i:=1 to n-1 do
write(a[i],' ');
writeln(a[n]);
halt;
end;
for i:=n-1 downto p+1 do
begin
t1:=true;
while t1 do
begin
t1:=false;
l:=maxlongint;
k:=0;
for j:=i+1 to n do
if (a[j]>a[i]) and (a[j]<l) then
begin
l:=a[j];
k:=j;
end;
if k<>0 then
begin
t:=a[i];
a[i]:=a[k];
a[k]:=t;
t1:=true;
qsort(i+1,n);
dec(ans);
try(i);
end;
end;
end;
end;

begin
readln(n);
readln(k);
for i:=1 to n do
read(a[i]);
ans:=k;
try(0);
end.//By Fkc

#include<algorithm>
#include<iostream>
using namespace std;
main()
{
int i,n,m,a[10001];
cin>>n>>m;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=m;i++)
next_permutation(a+1,a+n+1);
for(i=1;i<=n;i++)
cout<<a[i]<<' ';
}
跟楼下一个方法。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[10001];
main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=m;i++)
next_permutation(a+1,a+n+1);
for (int i=1;i<=n;i++)
cout<<a[i]<<' ';
}
algorithm函数库真心强大。连求下一个排列的函数都有。2004T4，15行代码秒杀！next_permutation万岁~

var
a:array[1..10000]of longint;
n,m,i,j,k,t,l:longint;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end;
procedure quicksoft(l,r:longint);
var
x,y,mid:longint;
begin
mid:=a[(l+r)div 2];x:=l;y:=r;
repeat
while a[x]<mid do inc(x);
while a[y]>mid do dec(y);
if x<=y then begin swap(a[x],a[y]);inc(x);dec(y);end;
until x>y;
if x<r then quicksoft(x,r);
if l<y then quicksoft(l,y);
end;
begin
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to m do
for j:=n downto 2 do
if a[j-1]<a[j] then
begin
t:=maxlongint;
for k:=j to n do if (a[k]<t)and (a[k]>a[j-1]) then
begin t:=a[k];l:=k;end;
swap(a[j-1],a[l]);
quicksoft(j,n);

break;
end;
for i:=1 to n do write(a[i],' ');
end.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
int n,m,temp;
cin >> n >> m;
vector<int> p;
for(int i=0;i<n;i++){
cin >> temp;
p.push_back(temp);
}
for(int i=0;i<m;i++) next_permutation(p.begin(),p.end());
vector<int>::iterator j;
for(j=p.begin();j!=p.end();j++) cout << *j <<" ";
//cout << "Hello world!" << endl;
return 0;
}

Orz下面所有的神牛。我什么都不懂，我只知道algorithm里面有个叫作next permutation的东西。。。

var
f,g:array[1..10001] of integer;

n,m,i,j,k,tt,p,q,c:integer;

procedure arraya;
begin
for p:=1 to n-i-1 do
for q:=p+1 to n-i do
if g[p]>g[q] then
begin
k:=g[p];
g[p]:=g[q];
g[q]:=k;
end;
end;

begin
readln(n);
readln(m);
for i:=1 to n do read(f[i]);
tt:=m;
while tt>0 do
begin
for i:=n downto 1 do
if f[i]<f then break;
c:=20000;
for j:=i+1 to n do
if (f[j]<c) and (f[j]>f[i]) then
begin c:=f[j]; k:=j; end;
c:=f[i];
f[i]:=f[k];
f[k]:=c;
for j:=i+1 to n do g[j-i]:=f[j];
arraya;
for j:=i+1 to n do f[j]:=g[j-i];
dec(tt);
end;
for i:=1 to n-1 do
write(f[i],' ');
writeln(f[n]);
end.

编译成功

测试数据 #0: Accepted, time = 62 ms, mem = 540 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 540 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 540 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 544 KiB, score = 10
Accepted, time = 92 ms, mem = 544 KiB, score = 100

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 10001
int a[MAX],n,m;

void fun()
{
int i,c=0,d=0,min;
for(i=n;i>1;i--)
if(a[i-1]<a[i])
{

break;
}
c=i-1;
int v=1;
if(i!=n)
{
for(;i<=n;i++)
{
if(a[c]<a[i] )
{

if(v)
{
min=a[i];
d=i;
v=0;
}
else if(a[i]<min)
{
min=a[i];
d=i;
}
}
}
}
else
d=n;
// cout<<"a[c] "<<a[c]<<" a[d]"<<a[d]<<endl;
int tem=a[c];
a[c]=a[d];
a[d]=tem;

sort(a+c+1,a+n+1);

}
int main()
{
int i;
while(cin>>n>>m)
{
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=m;i++)
fun();
for(i=1;i<n;i++)
cout<<a[i]<<" ";
cout<<a[i]<<endl;
}
return 0;
}

手动生成1-10000的排列肯定超时，而M才100，我们只要掌握生成任意一个排列的下一个即可；
通过自己模拟+2、+3等，就可知排列每次肯定都减少一个最靠近右侧的逆序对，如有A[J-1]《A[J]，那A[J-1]一定得更新了，因为不可能不变这个A[J-1]却还可以生成下一个排列（慢慢理解其实很简单）。而代替这个A[J-1]的是什么呢，那肯定也是A[J]-A[N]里面大于A[J-1]且最小的一个A[K]；然后对A[J]-A[N]排下序即是下一个排列；
如1 2 3 5 4，j-1为第3个3，则K为第5个4，交换后为1 2 4 5 3，然后再排序为1 2 4 3 5，这就是下一个排列。

我记得去年做这题，根本看不懂。。现在一看这么简单

因为n大，以前是想直接dfs，所以不会做。但是今天又看了看题目，觉得很水。

虽然n这么大，但是m只有100.纯粹模拟n，有很多时间是浪费。

可以直接用生成法。//so easy

生成法的原理：

1、j从最后往前面搜，找到第一个a[j-1]<a[j].

2、在从a[j]-a[n]中找到一个大于a[j-1]的最小数a[k]

3、swap（a[j-1],a[k]）

4、qsort(j,n),使他们从小到大排序。

这样一个排列就生成，如此做m次后，就是最后的答案！

经过一年的训练，能力增强。冲刺2013NOIp普及组一等！

SYF

想看跟详细的题解和程序。点 题解

想一起探讨Oi的孩纸门，可加QQ 841249284 峰哥，写明备注，欢迎所有人！

字典序法编程容易实现，而且求某个排列的下一个排列好使。

方法就是
如：2341
第一步：连续两数，满足左边<右边，并且要最靠右的，这里是34，记左边的下标为u.
编程的时候从右往左扫描，找到就BREAK.
第二步：以u位置的数3为准，找最靠右的大于它的数4。
把3，4互换，得到2431;
第三步：把u位置后面的数，反序.

2341->2431->2413

完毕.[感谢notblack大神提供思路]

#include<iostream>
using namespace std;
int main()
{
int n,m,i,j,k,l,t,h,a[20001],x;
cin>>n>>m;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=m;i++)
{
for(j=n;j>1;j--)
if(a[j]>a[j-1])
break;
h=j-1;
for(l=n;l>1;l--)
if(a[l]>a[h])
break;
k=a[l];a[l]=a[h];a[h]=k;
for(x=1;x<=n;x++)
a[x+n]=a[x];
for(t=2*n;h+1<=n;h++,t--)
a[h+1]=a[t];
}
for(i=1;i<n;i++)
cout<<a[i]<<" ";
cout<<a[n];
system("pause");
return 0;
}

这题一开始我想深搜成全排列，看看10000个手指就傻了。楼下那位大牛的题解让我豁然开朗，其实最多只需100次循环了，跟M有关。加油、加油！！
var i,j,n,k,m,c,w,t:longint;
a,b:array[1..10000]of longint;
procedure swap(var a,b:longint);
begin
c:=a;
a:=b;
b:=c;
end;
begin
readln(n);
readln(m);
for i:=1 to n do read(a[i]);
for i:=1 to m do begin
w:=n;while a[w-1]>a[w] do dec(w);
w:=w-1;
for j:=n downto w+1 do if a[j]>a[w] then begin
t:=j;
break;
end;
swap(a[w],a[t]);k:=n;
for j:=w+1 to n do b[j]:=a[j];
for j:=w+1 to n do begin
a[k]:=b[j];
dec(k);
end;
end;
write(a[1]);
for i:=2 to n do write(' ',a[i]);writeln;
end.