POJ 2718 Smallest Difference

http://poj.org/problem?id=2718

将所有数分成两部分各部分组成的数求差的绝对值最小

当个数为奇数n的时候分成n/2 位的为较小数部分 n/2+1位的为较大数这就很好取让较小数最大让较大数最小使得差最小

当个数为偶数的时候暂时没想到较好的贪心策略

但是因为只有10个数以内数据可以接受吧 10！ ≈ 3600000次

然后全排列取前一半后一半求差更新min_diff即可

刚好用到next_permitation()

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <math.h>
 6 using namespace std;
 7 
 8 const int INF = 0x7fffffff;
 9 int a[28], min_diff;
10 char num[128];
11 
12 long long pow10(int n)
13 {
14     long long ret = 1;
15     for (int i = 0 ;i < n; i++)
16     {
17         ret *= 10;
18     }
19     return ret;
20 }
21 
22 int to_number(int a[], int n, bool flag)//如果 flag为零 是组成最小数 如果最1 是组成最大数
23 {
24     int ans = 0;
25     if (!flag)//生成最小数
26     {
27         if (a[0] == 0 && n > 1)//消除0在最高位
28         {
29             swap(a[0], a[1]);
30         }
31         for(int i = 0; i < n; i++)
32         {
33             ans += a[i] * pow10(n-i-1);
34         }
35     }
36     else //生成最大数
37     {
38         for (int i = n-1; i >= 0; i-- )
39         {
40             ans += a[i] * pow10(i);
41         }
42     }
43     return ans;
44 }
45 
46 void solve(int n)
47 {
48     int set1[28], set2[28];
49     int s1 = 0, s2 = 0;
50     if (n % 2)//如果是奇数
51     {
52         //前 n / 2 + 1个都是 大数集合中的
53         for (int i = 0 ;i < n/2+1; i++)//set1存较大数
54         {
55             set1[s1++] = a[i];
56         }
57         for (int i = n/2+1;i < n; i++)//set2存较小数
58         {
59             set2[s2++] = a[i];
60         }
61         min_diff = abs(to_number(set1, s1, 0) - to_number(set2, s2, 1));
62     }
63     else
64     do{
65         s1 = 0;
66         s2 = 0;
67         for (int i = 0; i < n / 2; i++)
68         {
69             set1[s1++] = a[i];
70         }
71         for (int i = n / 2; i < n; i++)
72         {
73             set2[s2++] = a[i];
74         }
75         min_diff = min(min_diff, abs(to_number(set1, s1, 0) - to_number(set2, s2, 0)) );
76     }while (next_permutation(a, a+n));//直接全排列枚举 set1取前一半 set2取后一半
77 }
78 int main()
79 {
80     //797ms勉强飘过
81     freopen("in.txt", "r", stdin);
82     int n,t;
83     scanf("%d", &n);
84     getchar();
85     while(n--)
86     {
87         t = 0;
88         gets(num);
89         for (int i = 0; i < strlen(num); i++)
90         {
91             if (num[i] >= '0' && num[i] <= '9') a[t++] = num[i] - '0';
92         }
93         min_diff = INF;
94         solve(t);
95         printf("%d
",min_diff);
96     }
97     return 0;
98 }