Smallest Difference
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 2669 | Accepted: 763 |
Description
Given a number of distinct decimal digits, you can form one integer by choosing a non-empty subset of these digits and writing them in some order. The remaining digits can be written down in some order to form a second integer. Unless the resulting integer is 0, the integer may not start with the digit 0.
For example, if you are given the digits 0, 1, 2, 4, 6 and 7, you can write the pair of integers 10 and 2467. Of course, there are many ways to form such pairs of integers: 210 and 764, 204 and 176, etc. The absolute value of the difference between the integers in the last pair is 28, and it turns out that no other pair formed by the rules above can achieve a smaller difference.
For example, if you are given the digits 0, 1, 2, 4, 6 and 7, you can write the pair of integers 10 and 2467. Of course, there are many ways to form such pairs of integers: 210 and 764, 204 and 176, etc. The absolute value of the difference between the integers in the last pair is 28, and it turns out that no other pair formed by the rules above can achieve a smaller difference.
Input
The first line of input contains the number of cases to follow. For each case, there is one line of input containing at least two but no more than 10 decimal digits. (The decimal digits are 0, 1, ..., 9.) No digit appears more than once in one line of the input. The digits will appear in increasing order, separated by exactly one blank space.
Output
For each test case, write on a single line the smallest absolute difference of two integers that can be written from the given digits as described by the rules above.
Sample Input
1 0 1 2 4 6 7
Sample Output
28
题意就是说给几个数字（从0到9且不会重复），用这几个数字组成两个数，使他们差的绝对值最小
比如给0,1,2,4,6,7，那么构成204和176差最小，是28，而构成276,140就不是最小的了
我最初的思路就是先判断给的数字是奇数个还是偶数个
如果是偶数个，就先取两个相差最小且都非零的数作为各自的首位，剩下的数字中大的一半构成一个最大的数，加到刚才小的那个数字后面去，小的一半构成一个最小的数，加到刚才打的那个数字后面去，这样求出的两个数就差最小了
如果是奇数个，就先找一个最小的数作为一个数的开头，剩下的和偶数情况做法相同
但是这样做大概Wrong Answer了五六次，始终过不了，后来发现是偶数的情况有问题。
偶数情况第一步取两个相差最不且非零的数时，存在有多种选择的情况，也就是比如上面的例子0,1,2,4,6,7中，是选1,2作为开头还是选6,7做为开头无法确定。在这里我选择了暴力枚举的方法，把这几种情况都算一遍，反正最多也就9种情况。。。
就这样，困扰两天的题终于在没打表的情况下过了。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define INF 99999 5 6 using namespace std; 7 8 int num[11]; 9 bool select[11]; 10 char s[100]; 11 12 int power(int a,int b) 13 { 14 int result=1; 15 for(int i=1;i<=b;i++) 16 result*=a; 17 return result; 18 } 19 20 int main() 21 { 22 int kase; 23 24 scanf("%d",&kase); 25 getchar(); 26 27 while(kase--) 28 { 29 gets(s); 30 31 int len=strlen(s),a,b,x; 32 33 int t=0; 34 for(int i=0;i<len;i+=2,t++) 35 sscanf(&s[i],"%d",&num[t]); 36 for(int i=0;i<t;i++) 37 select[i]=false; 38 39 if(t%2==0) 40 { 41 int minx,miny; 42 if(num[0]==0&&t>2) 43 minx=1; 44 else 45 minx=0; 46 miny=minx+1; 47 for(int i=1;i<t-1;i++) 48 if(num[i+1]-num[i]<num[miny]-num[minx]) 49 { 50 miny=i+1; 51 minx=i; 52 } 53 int ans=INF; 54 for(int i=minx;i<t-1;i++) 55 { 56 x=t; 57 for(int j=0;j<t;j++) 58 select[j]=false; 59 select[i]=select[i+1]=true; 60 int a=num[i+1]*power(10,x/2-1); 61 int b=num[i]*power(10,x/2-1); 62 x-=2; 63 while(x) 64 { 65 int maxx=t-1; 66 while(select[maxx]) 67 maxx--; 68 select[maxx]=true; 69 int minx=0; 70 while(select[minx]) 71 minx++; 72 a+=num[minx]*power(10,x/2-1); 73 b+=num[maxx]*power(10,x/2-1); 74 select[minx]=true; 75 x-=2; 76 } 77 if(a-b<ans) 78 ans=a-b; 79 } 80 cout<<ans<<endl; 81 } 82 else 83 { 84 if(num[0]!=0) 85 { 86 select[0]=true; 87 a=num[0]*power(10,t/2); 88 b=0; 89 x=t-1; 90 } 91 else 92 { 93 select[1]=true; 94 a=num[1]*power(10,t/2); 95 b=0; 96 x=t-1; 97 } 98 while(x) 99 { 100 int maxx=t-1; 101 while(select[maxx]) 102 maxx--; 103 select[maxx]=true; 104 int minx=0; 105 while(select[minx]) 106 minx++; 107 a+=num[minx]*power(10,x/2-1); 108 b+=num[maxx]*power(10,x/2-1); 109 select[minx]=true; 110 x-=2; 111 } 112 cout<<a-b<<endl; 113 } 114 115 116 117 } 118 119 return 0; 120 }