拼凑正方形

[编程题]拼凑正方形

热度指数：97 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛有4根木棍,长度分别为a,b,c,d。羊羊家提供改变木棍长度的服务,如果牛牛支付一个硬币就可以让一根木棍的长度加一或者减一。牛牛需要用这四根木棍拼凑一个正方形出来,牛牛最少需要支付多少硬币才能让这四根木棍拼凑出正方形。

输入描述:

输入包括一行,四个整数a,b,c,d(1 ≤ a,b,c,d ≤ 10^6), 以空格分割

输出描述:

输出一个整数,表示牛牛最少需要支付的硬币

示例1

输入

4 1 5 4

输出

算法知识视频讲解

hey,20180424

初中数学题里面求绝对值的改编。简单举个例子，

有4个同学找个地方集合，位置分别在数轴上的 1，4，7 ，10. 应该找哪个位置呢，只要是4-7之间（包含4-7）的都可以，画个数轴一连接，图像很清楚。因为其他区域都会有重复范围，所以总和会变大。然后再想，如果有重复值有没有影响，答案是没有，可以举个例子试试。

所以代码就很容易了，利用数组的sort功能，把输入的四个值进行排序，都去第二个或者第三个点即可（第一个点的下标为0 一定注意！），用sort的时间复杂度是O( nlogn ) 所以整个算法的时间复杂度也是O( nlogn )

代码如下

   #include<iostream>  
   #include<cmath>  
   #include<algorithm>  
   using namespace std;  
   
  
   int main() {
     int len[4] = {};
     for (int i = 0; i < 4; ++i) {
         cin >>len[i] ;
     }
     sort(len, len + 4);
     int count = 0;
     for (int i = 0; i < 4; ++i)
         count += abs(len[i] - len[2]);
     cout << count << endl;
     return 0;
 }
  
  