Boxes and Candies [AtCoder Beginner Contest 048 C]

atcoder.jp

数列が与えられる。全ての隣り合う2項の和を x 以下にしたい。各項から引く値の総和の最小値はいくつか、という問題です。

入力例2で考えてみます。最初の2項は [1,6] ですが、これの和を1以下にしなくてはなりません。このとき、左側から1、右側から5引いて [0,1] とするのと、右側から6引いて [1,0] とするのではどちらが最適でしょうか。答えは右側から6引いた [1,0] です。なぜなら隣り合う2項のうち右側の項は次の比較でも使うからです。最初の2項 [a,b] を処理したあとは次の [b,c] を処理しなければなりません。このとき、右側の数字、すなわち [a,b] の b から優先的に引くことで、次の [b,c] の和を最初から減らした状態にすることができます。

したがってこの問題は、隣り合う2項を左から順に見ていって、もし和が x を超えているなら、右側の項から優先的に減らしていく、という処理を数列の最後まで走破させることで解くことができます。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt(), limitSum = sc.nextInt();
		int[] ar = new int[n];
		for (int i=0; i<n; i++) ar[i] = sc.nextInt();
		
		long ans = 0;
		for (int i=0; i<n-1; i++) {
			int tempSum = ar[i] + ar[i+1];
			if (tempSum > limitSum) {
				int minus = tempSum - limitSum;
				ans += minus;
				if (minus < ar[i+1]) {
					ar[i+1] -= minus;
				}
				else {
					minus -= ar[i+1];
					ar[i+1] = 0;
					ar[i] -= minus;
				}
			}
		}
		
		System.out.println(ans);
		
	}
}