首页 > 代码库 > 排列专题(不定期更新)

排列专题(不定期更新)

1、POJ  2718 Smallest Difference(穷竭搜索,枚举)

  题意:给出0~9之间的几个数,从给出的数中组合成两个新的整数(首位不为0),求两个数之间的差的绝对值的最小值。

  思路:由于最多只有10个数,全排列枚举,前n/2个形成一个数,后面的数字形成另一个数。

  

技术分享
 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<memory.h>
 5 #include<algorithm>
 6 using namespace std;
 7 int num[12];
 8 int used[12];
 9 int n;
10 int main()
11 {
12     int N;
13     cin >> N;
14     cin.ignore();
15     while (N--)
16     {
17         char c;
18         n= 0;
19         memset(used, 0, sizeof(used));
20         while (cin.get(c))
21         {
22             if (c ==  )continue;
23             else if (c == \n) break;
24             else num[n++] = c - 0;
25         }
26         if (n == 2)//考虑到两个数的特殊情况(错点)
27         {
28             cout << abs(num[1] - num[0]) << endl;
29             continue;
30         }
31         sort(num, num + n);
32         int ans = 1000000000;
33         do
34         {
35             if (num[0] == 0||num[n/2]==0) continue;
36             else
37             {
38                 int t1 = 0, t2 = 0;
39                 for (int i = 0; i < n / 2; i++) t1 = t1 * 10 + num[i];
40                 for (int i = n / 2; i < n; i++) t2 = t2 * 10 + num[i];
41                 if (abs(t2 - t1) < ans) ans = abs(t2 - t1);
42             }
43         } while (next_permutation(num, num + n));
44         printf("%d\n",ans);
45     }
46     return 0;
47 }
POJ 2718 Smallest Difference

 

排列专题(不定期更新)