POJ 2718 Smallest Difference(贪心 or next

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Smallest Difference

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.

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

Source

Rocky Mountain 2005

题意：给一升序集合集合中元素范围为1~9 从中寻找两个不相交子集（每个数只能用一次）求这两个子集组成两个整数的差最小值

这题要注意一个情况，除了组成的数只有0，否则都不能以0为开头，如01是不存在的，它并不等于1。如果输入012，那么答案是 10-2 = 8，并不是2-1（01） = 1。

分析：这道题数据量很小可以用next_permutation 来枚举所有的情况由于只是要找差最小所以枚举完只需要把枚举的情况从前到后组成两个位数相等（偶数情况）或者位数差1（奇数情况）的数然后相减取绝对值（避免先后问题），然后取这些情况的最小值即可。

next_permutation函数将按字母表顺序生成给定序列的下一个较大的序列，直到整个序列为减序为止,使用方法是next_permutation（begin(),end())。

代码中以一个地方写的很妙可以排除所有首元素为0的情况：

while(a[0] ==0)
next_permutation(a,a+cnt);//第一个数不能为0

因为next_permutation函数不会重复生成已经生成过的序列

这样就先排除了所有首数字为0的情况

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <cstring>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

char aa[];

int a[];

int cnt, mid, ans;

int main()

{

    int t;

    scanf("%d", &t);

    getchar();

    while(t--)

    {

        cnt = ;

        int t;

        while((t = getchar()) != '\n')

        {

            if(t != ' ')

            {

                aa[cnt] = t;

                cnt++;

            }

        }

        int mid = cnt/;

        ans = 1e9;

        if(cnt == )

        {

            printf("%d\n",aa[]-aa[]);

            continue;

        }

        for(int i = ; i < cnt; i++)

        {

            a[i] = aa[i] - '';

        }

        while(a[] ==)

            next_permutation(a,a+cnt);//第一个数不能为0

        do

        {

            if(a[mid])

            {

                int t1=,t2=;

                for(int i=;i<mid;++i)

                    t1=t1*+a[i];

                for(int i=mid;i<cnt;++i)

                    t2=t2*+a[i];

                ans=min(ans,abs(t1-t2));

                }

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

        printf("%d\n",ans);

    }

}

Next_permutation

前面说过这题数据量很小可以用枚举来实现复杂度为O（n²）但如果数据量增大枚举就行不通了这时候可以使用贪心的思想来做这道题。

设t1为大数 t2为小数

如果是奇数的情况那么因为t1的位数比t2多一位那么t1最高位挑选最小的元素 t2最高位挑选次小的元素然后t1依次挑选尽可能小的元素 t2依次挑选尽可能大的元素组成的数t1-t2就是答案

如果是偶数的情况那么就需要枚举一下每个相邻的位 t1的最高位挑选相邻位置中较大的元素 t2最高位挑选相邻位置较大的元素然后t1依次挑选尽可能小的元素 t2挑选尽可能大的元素

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <cstring>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

char aa[];

int a[];

int cnt, mid;

int main()

{

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

    //freopen("2.txt","w",stdout);

    int t;

    scanf("%d", &t);

    getchar();

    while(t--)

    {

        cnt = ;

        int t;

        while((t = getchar()) != '\n')

        {

            if(t != ' ')

            {

                aa[cnt] = t;

                cnt++;

            }

        }

        int mid = cnt/;

//        printf("%d\n",cnt);

        if(cnt == )

        {

            printf("%d\n",aa[]-aa[]);

            continue;

        }

        for(int i = ; i < cnt; i++)

        {

            a[i] = aa[i] - '';

        }

        if(cnt % == )//偶数情况

        {

            int t1,t2;//t1小数 t2大数

            bool vis[];

            memset(vis,,sizeof(vis));

            int ans = 1e9;

            for(int i = ; i < cnt-;i++)

            {

                if(a[i] == ) continue;

                t1 = a[i];

                t2 = a[i+];

//                printf("1  %d %d\n",t2, t1);

                vis[i]=;vis[i+] = ;

                int ti = ,pos = cnt - ;

                while(ti < cnt/- && pos >= )

                {

                    if(!vis[pos])

                    {

                        t1 = t1* + a[pos];

                        vis[pos] = ;

                        ti++;

                    }

                    pos--;

                }

                ti = ,pos = ;

                while(ti < cnt/- && pos < cnt)

                {

                    if(!vis[pos])

                    {

                        t2 = t2* + a[pos];

                        ti++;

                        vis[pos] = ;

                    }

                    pos++;

                }

                memset(vis,,sizeof(vis));

//                printf("2  %d %d\n",t2, t1);

                ans = min(ans,t2- t1);

            }

             printf("%d\n",ans);

        }

        else//奇数情况

        {

            int t1 , t2;//t1为大数 t2 为小数

            if(a[] != )

            {

                t1 = a[];

                t2 = a[cnt-];

                for(int i = ; i <= mid;i++)

                {

                    if(i == ) continue;

                    t1 = t1* + a[i];

                }

                for(int i = cnt-; i > mid; i--)

                {

                    t2 = t2* + a[i];

                }

                printf("%d\n",t1-t2);

            }

            else

            {

                t1 = a[];

                t2 = a[cnt-];

                for(int i = ; i <= mid;i++)

                {

                    if(i == ) continue;

                    t1 = t1* + a[i];

                }

                for(int i = cnt-; i > mid; i--)

                {

                    t2 = t2* + a[i];

                }

                printf("%d\n",t1-t2);

            }

        }

    }

}

贪心

巴特西

POJ 2718 Smallest Difference(贪心 or next_permutation暴力枚举)

最新文章

热门文章