P1088 [NOIP2004 大众组] 火星人

思路就是 全排列中找到题目所给的组合 然后加上的最小数就是往后面数几个组合 就是要求的那个排列 然后输出

• 我写的那一份代码ac了两个点 其他 全部tle 估计是比较的时间复杂度太高了
• 暴力写法的时间复杂度比内置函数要大很多
  
  暴力208ms 内置31ms

暴力

#include<bits/stdc++.h>
using namespace std;
int res[10010];
int num[10010];
int n,m;
int cnt;
bool flag;
void dfs(int x){
	if(flag==true) return;
   	if(x>n){
   		cnt++;
   		if(cnt==m+1){//到点输出
   			for(int i=1;i<=n;i++){
   				cout<<res[i]<<" \n"[i==n];
   			}
   			flag=true;
   		}
   	}
	for(int i=1;i<=n;i++){  
		if(cnt==0) i=res[x];//这一步相当于剪纸了 直接指向题目给的数组  可以自己cout一下
		if(num[i]!=1){
			num[i]=1;
			res[x]=i;
			dfs(x+1);
			num[i]=0;
		}else continue;
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cnt=0;
	memset(num,0,sizeof(num));
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>res[i];
	dfs(1);//开始深度搜索
	return 0;
}

内置函数

```#include<bits/stdc++.h>
using namespace std;
int res[10010];
int n,m;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
// 	cnt=0;
// 	memset(num,0,sizeof(num));
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>res[i];
    for(int i=1;i<=m;i++) next_permutation(res+1,res+1+n);  //next_permutation函数
	for(int i=1;i<=n;i++) cout<<res[i]<<" \n"[i==n];
	return 0;
}

next_permutation

有迭代器

bool customCompare(int a, int b) {
    return a > b; // 如果a大于b，则返回true，表示a应该在b之前  这样返回从大到小
}
其实和sort差不多 外面for循环就是生成多少个全排列 顺序是从小到大（默认）
格式：next_permutation(ord.begin() + 1, ord.begin() + 1 + n, customCompare)