poj2718

一、题意：给定一串数字，数字没有重复，个数为2~10个。求这些数字分为两份，组合成的两个数的差最小是多少

二、思路：首先可以肯定的是，将这n个数平均分成两份，所得到的最小差一定在其某个组合当中。因此可将该序列进行全排列，然后便利每一种情况。这里需要注意以下几点：1、利用next_permutation函数进行全排列前，需要将原序列按从小到大先排个序 2、要考虑这两个数不能以0开头的情况

三、代码：

#include"iostream"

#include"stdio.h"

#include"algorithm"

#include"string.h"

using namespace std;

int num[15];

int cnt;

int GetDiff(int *a)

{

    int n=0,m=0;

    if((a[0]==0||a[cnt/2]==0)&&cnt>2) return -1;

    for(int i=0;i<cnt/2;i++)

    {

        n=n*10+a[i];

    }

    for(int j=cnt/2;j<cnt;j++)

    {

        m=m*10+a[j];

    }

    return abs(n-m);

}

int Permutation()

{

    int miniDiff=10000000;

    do

    {

        int diff=GetDiff(num);

        if(diff!=-1)

            miniDiff=min(miniDiff,diff);

    }while(next_permutation(num,num+cnt));

    return miniDiff;

}

int main()

{

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

    int t;

    cin>>t;

    getchar();

    while(t--)

    {

        char input[100];

        gets(input);

        cnt=0;

        for(int i=0;i<strlen(input);i++)

        {

            if(isdigit(input[i]))

                num[cnt++]=input[i]-'0';

        }

        sort(num,num+cnt);

        cout<<Permutation()<<endl;

    }

    return 0;

}

巴特西

poj2718

最新文章

热门文章