原题如下:
无聊的幻想
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;
}
1 条评论
不错