ARC004-B 2点間距離の最大と最小

問題へのリンク

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("1");
            WillReturn.Add("1024");
            //1024
            //1024
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("5");
            //12
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            WillReturn.Add("512");
            WillReturn.Add("512");
            //1024
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("8");
            WillReturn.Add("1");
            //13
            //3
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("10");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("4");
            WillReturn.Add("5");
            WillReturn.Add("6");
            WillReturn.Add("7");
            WillReturn.Add("8");
            WillReturn.Add("9");
            WillReturn.Add("10");
            //55
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        var DistanceList = new List<long>();
        foreach (string EachStr in InputList.Skip(1)) {
            DistanceList.Add(long.Parse(EachStr));
        }

        DistanceList = DistanceList.OrderByDescending(pX => pX).ToList();
        if (DistanceList.Count == 1) {
            Console.WriteLine(DistanceList[0]);
            Console.WriteLine(DistanceList[0]);
            return;
        }
        if (DistanceList.Count == 2) {
            Console.WriteLine(DistanceList.Sum());
            Console.WriteLine(DistanceList[0] - DistanceList[1]);
            return;
        }

        long MaxVal = DistanceList[0];
        long RestSum = DistanceList.Skip(1).Sum();

        Console.WriteLine(DistanceList.Sum());
        if (MaxVal > RestSum) {
            Console.WriteLine(MaxVal - RestSum);
        }
        else {
            // 三角形の成立条件を満たすので0
            Console.WriteLine(0);
        }
    }
}

解説

最大値は自明で、全ての数の和です。
最小値について考えます。

要素数が1の場合、その数が最小値です。
要素数が2の場合、差が最小値です。

要素数が3の場合、
昇順でA B Cとします。
C >= A+B な場合は、C-A-Bが解です。
C < A+B な場合は、Cが最大なので |A-B| < C も成立し、
三角形の成立条件 |A-B| < C < A+B を満たすので
最小値は0となります。

要素数は4の場合は、
昇順でA B C Dとします。
D >= A+B+C な場合は、D-A-B-Cが解です。
D < A+B+C な場合は、Dが最大なので |(A+B)-C| < D も成立し、
三角形の成立条件 |(A+B)-C| < D < A+B+C を満たすので
最小値は0となります。

要素数5以上も同様です。