ABC-067-C Splitting Pile

■■■問題■■■

すぬけくんとアライグマはN枚のカードの山を作りました。
カードの山の上からi番目のカードには整数aiが書かれています。

N枚のカードを分け合うことにしました。

すぬけくんがカードの山の上から何枚かのカードを取ったあと、
アライグマは残ったカード全てを取ります。
このとき、すぬけくんもアライグマも1枚以上のカードを取る必要があります。

すぬけくんとアライグマが持っているカードに書かれた数の総和をそれぞれx,yとして、
|x−y| を最小化したいです。
|x−y| としてありうる値の最小値を求めなさい。

■■■入力■■■

N
a1 a2 ・・・ aN

●2 <= N <= 20万
●-10億 <= ai <= 10億
●aiは整数

■■■出力■■■

答えを出力せよ

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            WillReturn.Add("1 2 3 4 5 6");
            //1
            //すぬけくんが上から4枚のカードを、
            //アライグマが残った2枚のカードを取ったとき、
            //x=10,y=11 となって、|x-y| は1となり、これが最小です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("10 -10");
            //20
            //すぬけくんは上から1枚のカードを、アライグマは残った1枚を取るしかありえません。
            //このとき x=10,y=-10 となって、|x-y| は20となります。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        int UB = AArr.GetUpperBound(0);

        long TotalSum = 0;
        Array.ForEach(AArr, X => TotalSum += X);

        long Answer = long.MaxValue;

        long RunSum = 0;
        for (int I = 0; I <= UB - 1; I++) {
            RunSum += AArr[I];

            long RestSum = TotalSum - RunSum;

            long AnswerKouho = Math.Abs(RunSum - RestSum);
            if (Answer > AnswerKouho)
                Answer = AnswerKouho;
        }
        Console.WriteLine(Answer);
    }
}

解説

最初に山から取る枚数を全て試す方針で、
累積和を使って、計算量を減らしてます。