典型90問 070 Plant Planning（★4）

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("-1 2");
            WillReturn.Add("1 1");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1 0");
            WillReturn.Add("0 1");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("2 5");
            WillReturn.Add("2 5");
            WillReturn.Add("-3 4");
            WillReturn.Add("-4 -8");
            WillReturn.Add("6 -2");
            //35
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            WillReturn.Add("1000000000 1000000000");
            WillReturn.Add("-1000000000 1000000000");
            WillReturn.Add("-1000000000 -1000000000");
            WillReturn.Add("1000000000 -1000000000");
            //8000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XYInfoDef
    {
        internal long X;
        internal long Y;
    }
    static List<XYInfoDef> mXYInfoList = new List<XYInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XYInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mXYInfoList.Add(WillAdd);
        }

        long[] XArr = mXYInfoList.Select(pX => pX.X).ToArray();
        long[] YArr = mXYInfoList.Select(pX => pX.Y).ToArray();
        Array.Sort(XArr);
        Array.Sort(YArr);

        long UB = XArr.GetUpperBound(0);

        long Answer = 0;
        long MidX = XArr[UB / 2];
        long MidY = YArr[UB / 2];

        Answer += XArr.Sum(pX => Math.Abs(pX - MidX));
        Answer += YArr.Sum(pX => Math.Abs(pX - MidY));
        Console.WriteLine(Answer);
    }
}

解説

マンハッタン距離なので、X成分とY成分は分けて考えることができます。

X成分で見れば、配列の要素数が奇数なら、下記の図より
0 1 2 3 4
要素2に設定するのが最適と分かります。

配列の要素数が偶数なら、下記の図より
0 1 2 3 4 5
要素2か3に設定するのが最適と分かります。

なので、どっちの場合でも、配列の要素数 / 2 の位置
に設置するのが最適と分かります。