POJ 1833 排列

题意: 给你某个排列 求从下一个排列开始的第k个排列
如果是最后一个排列 则下一个排列为1 2 3 ... n
// 1 用stl 里面的 next_permutation
// 2 用生成下一个排列算法
// 1)从末尾开始找第一个正序 A[i-1]<A[i]
// 2)从i开始找最大的j A[j]>A[i-1]
// 3)交换 A[i-1],A[j]
// 4)将下标从i开始的序列翻转 #include <iostream>
#include <string>
#include<sstream>
#include <cmath>
#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int s[2000];
int n,k;
void change(int l,int r)
{
while(l<r)
{
swap(s[l],s[r]);
l++;
r--;
}
}
int main()
{
int T;
int i;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&k);
for(i=0;i<n;i++)
scanf("%d",&s[i]); while(k--) next_permutation(s,s+n);
for(i=0;i<n-1;i++)
printf("%d ",s[i]);
printf("%d\n",s[i]);
}
return 0;
} /* 2
#include <iostream>
#include <string>
#include<sstream>
#include <cmath>
#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int s[2000];
int n,k;
void change(int l,int r)
{
while(l<r)
{
swap(s[l],s[r]);
l++;
r--;
}
}
bool permutation()
{
int i=n-1;
while(i>0&&s[i-1]>=s[i]) i--;
if(!i) return false;
int k=i,j=n-1;
for(;j>i;j--)
if(s[j]>s[i-1]){
k=j;
break;
}
swap(s[i-1],s[k]);
change(i,n-1);
return true;
}
int main()
{
int T;
int i;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&k);
for(i=0;i<n;i++)
scanf("%d",&s[i]);
while(k--)
{
if(!permutation())
change(0,n-1);
}
for(i=0;i<n-1;i++)
printf("%d ",s[i]);
printf("%d\n",s[i]);
}
return 0;
}
*/

  

上一篇:JS复习:第二十二章


下一篇:redis使用watch完成秒杀抢购功能(转)