这题的思想是什么最简单的，为什么我对于下面的一个的实验不行：

1 4 6 2 9 5 8 7 3

从右往左扫描递减区域 :

1 4 6 2 9 5 (8 7 3)

用这个区域的前驱去跟这个递减区域中比这个前驱元素大且最接近这个前驱元素的数交换 :

1 4 6 2 9 7 (8 5 3)

然后对这个区域进行排序 :

1 4 6 2 9 7 (3 5 8)

就是下一个组合:

1 4 6 2 9 7 3 5 8

比如：1 2 3 4

-->1 2 4 3

->1 3 (4 2)-->1 3 2 4

-->1 3 4 2

后面的怎么办??不是又轮换到 1 2 (4 3)--> 1 2 3 4 ????

怎么回事,帮帮我...5555（呜）……

全排列，可以用O（MN）线性扫描，还有就是用个QSORT，也差不多

比如:

1 4 6 2 9 5 8 7 3

从右往左扫描递减区域 :

1 4 6 2 9 5 (8 7 3)

用这个区域的前驱去跟这个递减区域中比这个前驱元素大且最接近这个前驱元素的数交换 :

1 4 6 2 9 7 (8 5 3)

然后对这个区域进行排序 :

1 4 6 2 9 7 (3 5 8)

就是下一个组合:

1 4 6 2 9 7 3 5 8

O(m*n)

...我的DFS万能框架。。。

这个相当于不优化的裸搜。。。所以。。。直接DFS，如果某个位置已知，就只展开，否则穷举

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

提示：最后如果用冒泡全排会出错（经过多次实验得知，不过为什么错就不懂了）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

.............

1、先找一个比它后面还小的数；

2、再进行排序（小到大）；

zyy的程序是什么意思哦？

竞赛的时候我没做出来晕

zyy：

for j:=k+1 to (n-k) div 2+k do

　　 swap(a[j],a[n-(j-k-1)])

上面程序段如何推出的？？能不能告诉我方法~！

zyy 的程序很厉害啊！佩服佩服！

和全排列一个意思

反复调用贪心启发时间代价为M*N*logN

从n到1找第一个后面至少存在一个数比当前数大的数(记为i,位置为pos),放入hash表

然后从pos开始找一个比当i大最小的数

pos+1开始所有元素从hash表中释放出来

效率为n*m

还是可以通过题目数据:)

模拟。相邻的排列有这样的性质：

（1）可以肯定，相邻排列的前面若干个数字排列是相同的，只有某一个开始后面的不同。

（2）寻找这样的“不同位置起点”。这样的起点使得这个地方的数字的后面存在比它大的数。

（3）选取这些比它大的数中最小的一个，与刚才选出的起点数字交换。

（4）将从刚才的起点位置后一个数字开始直到最后的所有的数升序排序，即是比处理前的排列序号大一的排列。

依照这样的步骤，做m次后将结果输出即可。

这也许是有一定数学规律的吧？有人把这叫做贪心法。

题目是什么意思咯?看不懂,哪位大哥帮忙解释一下撒~~~

#include <iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<vector>
#include<cstring>
#include<algorithm>
#define mod 7654321
#define FOR(i,x,y) for(i=x;i<=y;++i)
#define maxa 10000+100
using namespace std;
int a[maxa];
int main()
{
    int n,m,i,t;
    cin>>n>>m;
    FOR(i,1,n)
    cin>>a[i];
    t = 0;
    do{
        if(t==m)
        break;
        t++;
    }while(next_permutation(a+1,a+n+1));
    FOR(i,1,n)
    cout<<a[i]<<" ";
}

搞了这么久结果一看题解STL大法好

#include<cstring>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<climits>
#include<vector>

using namespace std;

int n,m;
vector<int> w;

bool ce(int a,int b){
    return a>b;
}


void output(vector<int> ans){
    for (int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}

vector<int> cop(vector<int> now,vector<int> yet ,int a,int b){
    vector<int> ans=yet;
    for (int i=a;i<=b;i++){
        ans.push_back(now[i]);
    }
    return ans;
}

vector<int> find(vector<int> now,int tmp){
    vector<int> ans,bac;
    int p=-1;
    for (int i=0;i<now.size();i++){
        if (now[i]>tmp) p=now[i];
    }
    if (p==-1) return now;
    for (int i=0;i<now.size();i++){
        if (now[i]!=p) bac.push_back(now[i]);
    }
    ans.push_back(p);
    sort(bac.begin(),bac.end());
    ans=cop(bac,ans,0,bac.size()-1);
    return ans;
}

vector<int> pluse(vector<int> now){
    int i;
    for (int j=now.size()-1;j>=0;j--){
        if (now[j]>now[j-1]){
            i=j-1;
            break;
        }
    }
    vector<int> ans;
    
    vector<int> tmp;
    vector<int> afs=cop(now,tmp,i,now.size()-1);
    sort(afs.begin(),afs.end(),ce);
    vector<int> p=find(afs,now[i]);
    ans=cop(now,ans,0,i-1);
    ans=cop(p,ans,0,p.size()-1);
    
    //output(ans);
    return ans;
}

int main(void){
    //freopen("5.in","r",stdin);
    //freopen("1.out","w",stdout);
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        w.push_back(tmp);
    }
    for (int i=1;i<=m;i++) w=pluse(w);
    output(w);
    return 0;
}

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,s[10010],i=0;
int main(){
    scanf("%d%d",&n,&m)
    for(;i<n;++i) scanf("%d",s+i);
    for(i=0;i<m;++i) next_permutation(s,s+n);
    for(i=0;i<n;++i) printf("%d ",s[i]);
}

'''
#include <iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int b[10000+1];
int i,j,k,m,n,t;
void init() {
cin>>n>>m;
for(i=1; i<=n; i++)
cin>>b[i];
}
void out() {
for(i=1; i<=n-1; i++)
cout<<b[i]<<' ';
cout<<b[n]<<endl;
}
void work() {
for(i=1; i<=m; i++) { //增1 共M次
for(j=n-1; j>=1; j--) //找到最后可增加的位，即定位
if(b[j]<b[j+1])//例如12354加1，则只有3可增加位数
break;
for(k=n; k>=1; k--) //找到最小可增加的数字
if(b[k]>b[j])//例如12354加1，最小可增加的数字是4
break;
t=b[j];//交换，把原排列增大 ，
b[j]=b[k];//例如12354加1，即3和4交换，交换结果为12453
b[k]=t; //但12453并不是最终结果，而是12435即要排序
j=j+1;//向后移一位
k=n;
while((j<k)) { //把后面的逆序，相当于从小到大排序
t=b[j];
b[j]=b[k];
b[k]=t;
j++;
k--;
}
}
}
int main() {
init();
work();
out();
return 0;
}
'''C++