原题地址:https://ac.nowcoder.com/acm/contest/18839/1037
题目描述:
Compute, Cubercsl, SuperSodaSea, Ybmj 准备组队参加 "科大讯飞" 赞助的 CrossFire 比赛。
科大讯飞股份有限公司成立于1999年,。。阿巴阿巴阿巴,然后用人工智能建设美好世界。
这场比赛需要两人一队组队参加,他们不知道怎么分组。已知他们的 CrossFire 分数分别为 a, b, c, d,现在想要把他们两两分为一队,使得他们的实力比较平均,也就是两队的实力差尽量小。
这里定义两队的实力差为每队的 CrossFire 分数之和的差值,现在他们想要知道这个实力差最小是多少。
输入描述:
仅一行,包含四个整数 a, b, c, d (1≤a,b,c,d≤3681),中间以空格分隔,分别表示四个人的 CrossFire 分数。
输出描述:
在一行输出一个整数,表示两个队伍实力差的最小值。
这题可以直接比较三种情况的结果,但稍微想想可以直接直观的想到答案就是最大的和最小的分成一组。
接下来让我们来严密证明一下:
我们将不妨将abcd排个序,a>b>c>d,分为两组。
情况一:(a,b)(c,d),我们可以直接看出这是差两组和的最大(最大的两个数见最小的两个数,结果肯定最大)。
情况二:(a,c)(b,d),设差为x,则有x=a+c-b-d。
情况三:(a,d)(b,c),设差为y,则有y=a+d-b-c。
此时我们用高中常用的思想:着差比较思想,x-y=(a+c-b-d)-(a+d-b-c)=2c-2d>0
———————————————————————————— x>y
然而并没有结束,根据题意,我们要的是两组成绩的差值,都是正整数,而真实情况存在x>0,y<0的情况
(例如:a=6,b=5,c=4,d=1,此时x=2,y=-2就不符合题意。)
这意味着我们要对x和y取绝对值,才符合题意。所以接下来比较|x|与|y|的大小:
因为x>y,所以y>0时,x>0,绝对值直接去掉了;
而x=(a+c)-(b+d)=(a-b)+(c-d)>0
——————— x>0
所以只有x>0,y<0这种情况需要我们直接考虑。
此时|x|-|y|=x-(-y)=x+y=(a+c-b-d)+(a+d-b-c)=2a-2b>0
——————————————————|x|>|y|
到此得证,最大的和最小的分成一组为答案。
写代码时,我们发现要将这四个数排序挺麻烦的,我们需要转换一下思路:
我们输出的答案表达式为y,即(a+d)-(b+c),两边同时加上(b+c),得(a+b+c+d)-2(b+c),现在就很方便求了,我们只需求得最大值和最小值(用max()函数和min()函数),再将所求结果取绝对值(用绝对值函数fabs())就行啦!
还没完!
我在写代码的时候就报错了,因为fabs()函数的返回值是int,在这里提醒一下大佬们。
还有头文件别忘了
代码如下:
#include<iostream> #include<algorithm> #include<math.h> using namespace std; int main() { int a,b,c,d; int minn,maxn; scanf("%d %d %d %d ",&a,&b,&c,&d); minn=min(min(a,b),min(c,d)); maxn=max(max(a,b),max(c,d)); printf("%d",(int)fabs((maxn+minn)*2-a-b-c-d)); return 0; }