POJ 2718 -- Smallest Difference

POJ 2718 Smallest Difference
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.
http://www.hankcs.com/program/poj-2718-smallest-difference-challenge-programming-contest-2nd-edition-exercises-answers.html

将一个数切一刀拆成两个数，两个数每一位数字的顺序都可改变，但是不能有前导0。求这两个数之差的最小值。

于是继续走搜索的路线，上面的程序之所以慢，是因为重复计算。比如第一个字串为12，第二个字串为34这种情况和第一个字串为34，第二个字串为12这种情况被视作不同的情况。这是应当被优化的第一个点。

第二个点是string类型的全排操作比较费时，可以用位运算优化。

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int n;

    cin >> n;

    cin.ignore();

    while (n--)

    {

        string all;

        getline(cin, all);

        all.erase(remove(all.begin(), all.end(), ' '), all.end());

        int length = all.size();

        int cut = length / 2;

        int permute = 1 << length;

        int result = 0x3F3F3F3F;

        do

        {

            bitset<10> used = static_cast<bitset<10>>(permute);

            string s1, s2;

            for (int i = 0; i < length; ++i)

            {

                if (used[i])

                {

                    s1 += all[i];

                }

                else

                {

                    s2 += all[i];

                }

            }

            if (s1.size() != cut)

            {

                continue;

            }

            if (s1[0] == '0' && s1.size() > 1)

            {

                continue;

            }

            // s1 s2 已经被切割出来了

            // 穷举它们

            do

            {

                int n1 = atoi(s1.c_str());

                do

                {

                    if (s2[0] == '0' && s2.size() > 1)

                    {

                        continue;

                    }

                    int n2 = atoi(s2.c_str());

                    int dif = abs(n1 - n2);

                    //cout << s1 << ' ' << s2 << " dif " << dif << " result: " << result << endl;

                    if (dif < result)

                    {

                        result = dif;

                    }

                } while (next_permutation(s2.begin(), s2.end()));

            } while (next_permutation(s1.begin(), s1.end()));

        } while (--permute);

 

        cout << result << endl;

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

首先除以二，使得2边平均，然后2次dfs分别枚举a和b，更新ans。

注意0可以单独存在，但不能作为前导0.//我这里被坑了。

思路：直接枚举一半，然后枚举组合数，简单暴力。
http://blog.csdn.net/u010709592/article/details/17282927

1. void dfs2(int len)  
2. {  
3.     int top1=0;  
4.     int top2=0;  
5.   
6.     for(int i=0;i<M.size();i++)  
7.     {  
8.         if(vis[i])lef[top1++]=M[i];  
9.         else rig[top2++]=M[i];  
10.     }    
11.     do  
12.     {  
13.         int val1=getval1(top1);  
14.         do  
15.         {  
16.             int val2=getval2(top2);  
17.             if(abs(val1-val2)<ans)  
18.             {  
19.                // printf("%d %d\n",val1,val2);  
20.                 ans=abs(val1-val2);  
21.             }  
22.         }while(next_permutation(rig,rig+top2));  
23.     }while(next_permutation(lef,lef+top1));  
24. }  
25.   
26. void dfs1(int len,int pos,int dep)  
27. {  
28.     if(dep>len)  
29.     { 
30.         dfs2(len);  
31.         return;  
32.     }  
33.     for(int i=pos;i<n;i++)  
34.     {  
35.         vis[i]=true;  
36.         dfs1(len,i+1,dep+1);  
37.         vis[i]=false;  
38.     }  
39. }    
40. int main()  
41. {  
42.     int T;  
43.     scanf("%d",&T);  
44.     getchar();  
45.     while(T--)  
46.     {  
47.         M.clear();  
48.         memset(vis,false,sizeof vis);  
49.         ans=0x3f3f3f3f;  
50.         char ch;  
51.         int a;  
52.         do  
53.         {  
54.             scanf("%d%c",&a,&ch);  
55.             M.push_back(a);  
56.         }while(ch!='\n');  
57.         n=M.size();  
58.         dfs1(n/2,0,1);  
59.         printf("%d\n",ans);  
60.     }  
61.     return 0;  
62. } 

Read full article from 2718 -- Smallest Difference