原题如下:
无聊的幻想
1000(ms) 10000(kb) 9 / 72
SRC有天在吃饭的时候,看着食堂的同学们整齐的坐在餐桌两边。突然想到: 现在有一个8位长的数字(不足8位的用0补齐,如:1 输入为00000001)。SRC会一种换位魔法可以将任意一位换为0-9的数字,但是一次只能换一位数字。怎么样才能使得前4位的每位数字之和等于后4位每位数字之和,并且使用魔法的次数最少?

输入
多组输入
每组一个8位的数字(正整数)
输出
使用魔法的最少次数
样例输入
00000001
11111111
样例输出
1
0

一开始通过比较一边的大小,即比如输入 123444554

直接排序左右4个排序,即如下:
1 2 3 4 4 4 5 5
然后分好大的和小的
在将小的的最小值改成9
再两边重新求和。

9 2 3 4 4 4 5 5
18 18
9+2+3+4-4-4-5-5>=0 && <=9
如果成立就退出,否则就重新排序,继续判断。
这样只考虑了一半,假如出现 5555 4499
这种,就不一定会出现最优解了,所以必须判断用大的还是用小的,具体看代码:
AC代码如下:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
    string num;

    while (cin >> num)
    {
        int Count = 0;


        sort(&num[0], &num[4]);
        sort(&num[4], &num[8]);

        int s1 = 0;
        int s2 = 0;

        for (int i = 0; i < 4; i++)
        {
            s1 += num[i] - '0';
        }

        for (int i = 4; i < 8; i++)
        {
            s2 += num[i] - '0';
        }

        int num1[4];
        int num2[4];
        if (s1 > s2)
        {
            for (int i = 0; i < 4; i++)
            {
                num1[i] = num[i] - '0';
                num2[i] = num[i + 4] - '0';
            }
        }
        else if (s1 < s2)
        {
            for (int i = 0; i < 4; i++)
            {
                num2[i] = num[i] - '0';
                num1[i] = num[i + 4] - '0';
            }
        }
        int maxsum = s1 > s2 ? s1 : s2;
        int minsum = s1 > s2 ? s2 : s1;
        while (maxsum != minsum)  //num1是大的  num2是小的
        {
            Count++;
            int a1 = 9-num1[3];
            int a2 = num2[0];
            if(a1 <= a2)
            {
                if(maxsum-num1[3]-minsum<=0 && maxsum-num1[3]-minsum>=-9)   //关键
                {
                    break;
                }
                else
                {
                    num1[3] = 0;
                    sort(&num1[0], &num1[4]);
                    maxsum = 0;
                    for(int i=0;i<4;i++)
                    {
                        maxsum+=num1[i];
                    }
                }
            }
            else   //同
            {
                if(minsum-num2[0]+9-maxsum >= 0 &&minsum-num2[0]+9-maxsum  <=9 )
                {
                    break;
                }
                else
                {
                    num2[0] = 9;
                    sort(&num2[0], &num2[4]);
                    minsum = 0;
                    for(int i=0;i<4;i++)
                    {
                        minsum+=num2[i];
                    }   
                }
            }
    }
        cout << Count << endl;
    }
    return 0;
}
最后修改:2019 年 04 月 25 日 08 : 16 PM
如果觉得我的文章对你有用,请随意赞赏