这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址:
http://poj.grids.cn/problem/1833/
此题有两种方法:
方法一:利用STL里的next_permutation()函数,当然,这样题就水了。
方法二:模拟,找出数列变化的特点。排列过程待补。。。大家记得提醒我。
直接发代码了。
方法一:(STL)
// Grid 1833
// Author: Tanky Woo
#include
#include
using namespace std;
#define MAX 1034
int ans[MAX];
// www.wutianqi.com
int main()
{
int nCases;
int num, k, i, j;
scanf("%d", &nCases;);
while(nCases--)
{
scanf("%d %d", #, &k;);
for(i = 1; i <= num; ++i)
scanf("%d", &ans;[i]);
for(i = 0; i < k; ++i)
next_permutation(ans+1, ans+num+1);
for(j = 1; j <= num; ++j)
printf("%d ", ans[j]);
printf("\n");
}
return 0;
}
方法二:(模拟)
// Grid 1833
// Author: Tanky Woo
#include
using namespace std;
#define MAX 1034
int ans[MAX];
int MyCompare(const void *e1, const void *e2)
{
return *((int*) e1) - *((int*) e2);
}
// www.wutianqi.com
int main()
{
int nCases;
int num, k, i, j;
scanf("%d", &nCases;);
while(nCases--)
{
scanf("%d %d", #, &k;);
for(i = 1; i <= num; ++i)
scanf("%d", &ans;[i]);
ans[0] = 1000000; //ans[0]是哨兵,确保ans[0]比其他都大
for(i = 0; i < k; ++i) //每次循环都找出下一个排列
{
for(j = num; j >= 1 && ans[j-1] > ans[j]; --j)
;
if(j >= 1)
{
int nMinLarge = ans[j];
int nMinId = j;
//下面找出从ans[j]及其后最小的比ans[j-1]大的元素,并记住其下标
for(int kk = j; kk <= num; ++kk)
if(nMinLarge > ans[kk] && ans[kk] > ans[j-1])
{
nMinLarge = ans[kk];
nMinId = kk;
}
//交换位置
ans[nMinId] = ans[j-1];
ans[j-1] = nMinLarge;
qsort(ans+j, num-j+1, sizeof(int), MyCompare);
}
else
for(j = 1; j <= num; ++j)
ans[j] = j;
}
for(j = 1; j <= num; ++j)
printf("%d ", ans[j]);
printf("\n");
}
return 0;
}