ABC-048-C Boxes and Candies

■■■問題■■■

N個の箱が横一列に並んでいます。最初、左からi番目の箱にはai個のキャンディが入っています。
すぬけ君は次の操作を好きな回数だけ行うことができます。
●キャンディが1個以上入っている箱をひとつ選び、その箱のキャンディを1個食べる。

すぬけ君の目標は次の通りです。
●どの隣り合う2つの箱を見ても、それらの箱に入っているキャンディの個数の総和がx以下である。

目標を達成するために必要な操作回数の最小値を求めてください。

■■■入力■■■

N x
a1 a2 ・・・ aN

●2 <= N  <= 10万
●0 <= ai <= 10億
●0 <= x  <= 10億

■■■出力■■■

目標を達成するために必要な操作回数の最小値を出力せよ。

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("3 3");
            WillReturn.Add("2 2 2");
            //1
            //2番目の箱のキャンディを1個食べればよいです。
            //すると、各箱のキャンディの個数は(2,1,2)となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 1");
            WillReturn.Add("1 6 1 2 0 4");
            //11
            //たとえば、2番目の箱のキャンディを6個食べ、
            //4番目の箱のキャンディを2個食べ、
            //6番目の箱のキャンディを3個食べればよいです。
            //すると、各箱キャンディの個数は(1,0,1,0,0,1)となります。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 9");
            WillReturn.Add("3 1 4 1 5");
            //0
            //最初から目標が達成されているので、操作を行う必要はありません
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("2 0");
            WillReturn.Add("5 5");
            //10
            //すべてのキャンディを食べなければなりません
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();

        long x = wkArr[1];
        long[] AArr = InputList[1].Split(' ').Select(X => long.Parse(X)).ToArray();

        long SousaCnt = 0;
        for (int I = 0; I <= AArr.GetUpperBound(0) - 1; I++) {
            long CurrSum = AArr[I] + AArr[I + 1];

            Action<int> wkAct = (pTargetInd) =>
            {
                if (CurrSum > x) {
                    long EatCnt = Math.Min(CurrSum - x, AArr[pTargetInd]);
                    CurrSum -= EatCnt;
                    SousaCnt += EatCnt;
                    AArr[pTargetInd] -= EatCnt;
                }
            };
            wkAct(I + 1);
            wkAct(I);
        }
        Console.WriteLine(SousaCnt);
    }
}

解説

左のほうにある箱のペアから、
右の箱優先でキャンディを食べる方法をシュミレーションしてます。