思路就是 全排列中找到题目所给的组合 然后加上的最小数就是往后面数几个组合 就是要求的那个排列 然后输出
- 我写的那一份代码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)
