首页 > 代码库 > 排列专题(不定期更新)
排列专题(不定期更新)
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 }
排列专题(不定期更新)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。