poj 2718 Smallest Difference 搜索

缘起

日常水题 poj 2718 Smallest Difference

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
给你0~9中不同的几个数字（因此个数<=10）要求你使用这些数字组成2个数字，要求他俩的差的绝对值最小.
例如 给你0, 1, 2, 4, 6 ,7,  则组成 204和176，他俩的差距是28, 这是你能找到的最小的差距了.
所以你需要输出28

【输入】
多样例. 每个样例由不超过10个数字构成（数字在0~9中挑选），数字都是不重复的. 而且这些数字将递增给出

【输出】
对每个样例，输出最小差距

【样例输入】
1
0 1 2 4 6 7

【样例输出】
28

【限制】
Time limit1000 ms 
Memory limit 65536 kB

【来源】
Rocky Mountain 2005

枚举全排列即可. 用到 c++ stl中较有用的一个api——next_permutation

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
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <sstream>
using namespace std;
//#define LOCAL
#define DIS(x,y) ((x)>(y)?((x)-(y)):((y)-(x)))

int a[15];
char s[105];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	getchar(); // scanf不会要换行符的, 换行符依旧停留在缓冲区, 所以需要getchar吸收掉
	while(t--)
	{
		stringstream ss;
		gets(s);
		ss << s;
		int n = 0; // n是数组元素的个数
		while(ss>>a[n])n++; // 本题的IO较为恶心
		int ans = 0x3f3f3f3f;
		do 
		{
			if ((!a[0]&&n>3)||(!a[n>>1]&&n>2)) // 题目要求不能有前导零
			{
				continue;
			}
			int i = 0,x=0,y=0;
			while(i<(n>>1)) // 洪特规则
			{
				x = x*10+a[i];
				i++;
			}
			while(i<n)
			{
				y=y*10+a[i];
				i++;
			}
			if (ans>DIS(x,y))
			{
				ans = DIS(x,y);
			}
		} while (next_permutation(a, a+n));
		printf("%d\n",ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 454ms
Memory 160kB
Length 874
Lang C++
Submitted 2019-08-23 21:47:57
Shared
RemoteRunId 20793575