首页 > 代码库 > 是时候学一波STL了。。。
是时候学一波STL了。。。
都到如今了还不会STL,赶紧学习一下。
。。
头文件#include<algorithm>
加上 using namespace std。
求下一个排列的函数:next_permutation(first,last),当中first,last都是指针变量。求的是区间
[first。last)的下一个排列。升序求得。比若说1 2 3 下一个排列是1 3 2。最后一个排列的下一个排列是第
一个。即3 2 1——>1 2 3。据说效率也不怎么样,poj 1833用G++交TLE。C++过了.
假设当前是最后一个排列,则next_permutation(first,last)会返回false。
。。
实现原理:
在当前序列中,从尾端往前寻找两个相邻元素。前一个记为*i,后一个记为*ii。而且满足*i < *ii。
然后再从尾
端寻找还有一个元素*j,假设满足*i < *j,即将第i个元素与第j个元素对调,并将第ii个元素之后(包含ii)的所
有元素颠倒排序,即求出下一个序列了。
prev_permutation(first,last)是求的前一个排列。。。
id=1833">poj 1833
代码:
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; int a[1025]; int main() { int T,m,n; scanf("%d",&T); while(T--) { scanf("%d%d",&m,&n); for(int i=0; i<m; i++) { scanf("%d",&a[i]); } int *first = a; int *last = a+m; while(n--) { next_permutation(first,last); } for(int i=0; i<m; i++) { printf("%d",a[i]); if(i!=m-1) { printf(" "); } } puts(""); } return 0; }
id=1731">poj 1731
样例。用来练手。。。
代码:
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; int cmp(const void *a,const void *b) { return *(char *)a-*(char *)b; } int main() { char a[205]; scanf("%s",a); int len = strlen(a); qsort(a,len,sizeof(a[0]),cmp); char *sta = a; char *end = a+len; puts(a); while(next_permutation(sta,end)) { puts(a); } return 0; }
是时候学一波STL了。。。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。