题目描述

给定若干位十进制数，你可以通过选择一个非空子集并以某种顺序构建一个数。剩余元素可以用相同规则构建第二个数。除非构造的数恰好为0，否则不能以0打头。

举例来说，给定数字0，1，2，4，6与7，你可以写出10和2467。当然写法多样：210和764，204和176，等等。最后一对数差的绝对值为28，实际上没有其他对拥有更小的差。

输入

输入第一行的数表示随后测试用例的数量。
对于每组测试用例，有一行至少两个不超过10的十进制数字。（十进制数字为0，1，…，9）每行输入中均无重复的数字。数字为升序给出，相隔恰好一个空格。

输出

对于每组测试用例，输出一个以上述规则可获得的最小的差的绝对值在一行。

样例

1
0 1 2 4 6 7

28

算法1

全排列枚举

使用next_permutation函数

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
using namespace std;
const int N=1010;
int a[N],len;
int n;

int main()
{
    int T;
    cin>>T;
    cin.ignore();
    while(T--)
    {
        len=0;
        string line;
        getline(cin,line);
        stringstream ss(line);
        int x;
        while(ss>>x) a[len++]=x;

        if(len == 2)
        {
            cout<<abs(a[0]-a[1])<<endl;
            continue;
        }

        int ans=1e9;
        do
        {
            int t1=a[0],t2=a[len/2];
            if(!t1 || !t2) continue;

            for(int i=1;i<len/2;i++) t1=t1*10+a[i];

            for(int i=len/2+1;i<len;i++) t2=t2*10+a[i];

            ans=min(ans,abs(t1-t2));
        }while(next_permutation(a,a+len));

        cout<<ans<<endl;
    }

   // system("pause");
}

算法2

贪心

1.长度为奇数：拼凑两个数a1, a2, a1 < a2,

• a2比a1多一位，自然a2的最高位应最小，如果最小值为0则a2的最高位取次小。
• 此时a2的剩下数位要保证尽量小，a1剩下的数位要保证尽量大。

2.长度为偶数：拼凑两个数a1,a2, a1 < a2, 且a1和a2一样长，自然a1和a2的最高位应该取相差最小的数

• 注意a1的最高位不能有前导零（0除外）
• a1和a2的最高位确定之后，a1的剩下数位要保证尽量大，a2剩下的数位要保证尽量小。

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
using namespace std;
const int N=1010;
int a[N],len;
int n;

int fun1()
{
    int mid=len/2+1;

    if(a[0] == 0) swap(a[0],a[1]);

    int t1=0;
    for(int i=0;i<mid;i++) t1=t1*10+a[i];

    int t2=0;
    for(int i=len-1;i>=mid;i--) t2=t2*10+a[i];

    return abs(t1-t2);
}

int calc(int t)
{
    vector<int> b;
    for(int i=0;i<len;i++)
        if(i==t) i++;
        else b.push_back(a[i]);

    int t1=a[t];
    int mid=b.size()/2;
    for(int i=b.size()-1;i>=mid;i--) t1=t1*10+b[i];

    int t2=a[t+1];
    for(int i=0;i<mid;i++) t2=t2*10+b[i];
    //cout<<"---"<<t1<<' '<<t2<<endl;
    return abs(t1-t2);

}

int fun2()
{
    if(len == 2) return abs(a[0]-a[1]);

    int mn=1e9;
    int t=0;
    int ans=1e9;
    for(int i=0;i<len-1;i++)
    {
        if(abs(a[i]-a[i+1]) <= mn && a[i])
        {
            mn=abs(a[i]-a[i+1]);
            t=i;
            ans=min(ans,calc(t));
        }
    }

    return ans;
}

int main()
{
    int T;
    cin>>T;
    cin.ignore();
    while(T--)
    {
        len=0;
        string line;
        getline(cin,line);
        stringstream ss(line);
        int x;
        while(ss>>x) a[len++]=x;

        if(len & 1) printf("%d\n",fun1());
        else printf("%d\n",fun2());
    }

   // system("pause");
}

参考

https://www.acwing.com/blog/content/1959/