百练Grid POJ 1833 排列

题目地址:

http://poj.grids.cn/problem/1833/

此题有两种方法:

方法一:利用STL里的next_permutation()函数,当然,这样题就水了。

方法二:模拟,找出数列变化的特点。排列过程待补。。。大家记得提醒我。

直接发代码了。

方法一:(STL)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Grid 1833
// Author: Tanky Woo
#include <iostream>
#include <algorithm>
 
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", &num, &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;
}

方法二:(模拟)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Grid 1833
// Author: Tanky Woo
#include <iostream>
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", &num, &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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《百练Grid POJ 1833 排列》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注