首页 > 代码库 > 是时候学一波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了。。。