首页 > 试题广场 >

拼凑正方形

[编程题]拼凑正方形
  • 热度指数:65 时间限制: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

输出

4
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            list.add(sc.nextInt());
        }
        Collections.sort(list);

        List<Integer> results = new ArrayList<>();
        for (int i = list.get(0); i <= list.get(3) ; i++) {
            int count = 0;
            for (int j = 0; j < 4; j++) {
                if (list.get(j) >= i){
                    count += (list.get(j)-i);
                }else {
                    count += (i - list.get(j));
                }
            }
            results.add(count);
        }

        Collections.sort(results);
        System.out.println(results.get(0));
    }
}
发表于 2018-01-24 21:44:58 回复(0)
直接穷举,运算计算出最终结果,循环次数确定且次数较小,O(n2)时间复杂度也很快
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] input = new int[4];
        for (int i=0; i<4; i++)
            input[i] = in.nextInt();
        System.out.println(getMin(input));
    }  
     
    static int getMin(int[] input) {
        int min = Integer.MAX_VALUE;
        for (int i=0; i<4; i++) {
            int sum=0;
            for (int j=0; j<4; j++)
                sum += Math.abs(input[i]-input[j]);
            min = Math.min(min, sum);
        }
        return min;
    }
}


发表于 2019-12-04 17:47:13 回复(0)
def findCost(array):
    minVal = min(array)
    maxVal = max(array)
    minCost = 1e9
    for num in range(minVal, maxVal+1):
        temp_cost = 0
        for j in range(4):
            temp_cost += abs(num - array[j])
        minCost = min(minCost, temp_cost)
    return minCost

inputArr = list(int(x) for x in input().split(" "))
print(findCost(inputArr))
        


发表于 2021-03-21 12:56:38 回复(0)

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

int main()
{
    int a[4];
    int i;
    for(i=0;i<4;i++) cin>>a[i];
    sort(a,a+4);
    cout<<a[3]+a[2]-a[1]-a[0]<<endl;
    return 0;
}

发表于 2018-01-27 11:40:53 回复(0)