POJ 2718 Smallest Difference

Description

给出不重复的几个数字，将他们分成两部分，组成两个数字，求所有情况中差值最小时的差值

注意点

1. 若有0，则0必须用上
2. 我之前认为，划分123时要划分成12、3与1、23，后来发现next_permutation会产生一个231，他划分可出23、1就是前面的1 、23

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;


int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int a[12];
        int cnt = 0;
        char ch;
        while(1)
        {
            scanf("%d%c", &a[cnt++], &ch);
            if(ch == '\n')
                break;
        }
        int ans = 0x3f3f3f3f;
        if(cnt == 2)
        {
            cout << abs(a[0] - a[1]) << '\n';
            continue;
        }
        do
        {
            int tem_fro = 0;
            if(a[0] == 0 || a[cnt / 2] == 0)
                continue;
            for(int i = 0; i < cnt / 2; ++i)
                tem_fro = tem_fro * 10 + a[i];
            int tem_bac = 0;
            for(int i = cnt / 2; i < cnt; ++i)
                tem_bac = tem_bac * 10 + a[i];
            int tem = abs(tem_fro - tem_bac);
            if(tem < ans)
                ans = tem;
        }while(next_permutation(a, a + cnt));
        cout << ans << '\n';
    }
    return 0;
}