算法1
可以用库函数next_permutation 求得下一个排列
我们这里就手写一下这个函数
next_permutation:
举个例子 比如 2 3 5 4 1这几个数字 从后看第一个非降序的数位是1(也就是数字3) 我们将它记录下来
然后从后面降序的几个数字中找到比他大的最小的数字也就是4 将它们交换位置 即 2 4 5 3 1 然后我们再把
后面降序的几个数字排序一下 得到此时的最小字典序 所以最终得到了 2 4 1 3 5
这道题中我们只需要调用m次这个函数即可
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
vector<int> num;
void next(vector<int> &num)
{
int k = num.size() - 1;
while(num[k] < num[k-1] && k > 0) k--;
if(k<=0)//若当前字典序最大 则下一个排列则为最小字典序排列
{
reverse(num.begin(),num.end());
}
else
{
int t = k;
while(num[k-1] < num[t] && t < num.size()) t++;
swap(num[k-1],num[t-1]);
sort(num.begin() + k ,num.end());
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
int x;cin>>x;
num.push_back(x);
}
while(m--)
{
next(num);
}
for(auto it : num) cout<<it<<" ";
}