問題概要

$N$ 個の非負整数からなる数列 $a_{1}, a_{2}, \dots, a_{N}$ が与えられる。この数列に対して、

「正の整数である要素を 1 つ選び、-1 する」

という操作を繰り返すことで、どの隣接する 2 個の要素の和も $x$ 以下となるようにしたい。

これを実現するための最小操作回数を求めよ。

制約

$2 \le N \le 10^{5}$
$0 \le a_{i}, x \le 10^{9}$

考えたこと

この手の問題では「端から順に考えていく」ことが有効であることが多々ある。今回も左端の 2 要素 $a_{1}$ と $a_{2}$ について考えてみよう。

ここでパッと思いつくことは、 $a_{1}$ を減らすよりも、 $a_{2}$ を減らした方が、後々得であるということだ。より詳しく言えば、 $a_{1}$ を減らしても $a_{1} + a_{2} \le x$ という制約にしか効いてこないが、 $a_{2}$ を減らすと $a_{1} + a_{2} \le x$ という制約だけでなく $a_{2} + a_{3} \le x$ という制約にも効いてくるのだ。

というわけで、基本的には $a_{2}$ を減らすこととする。ただし注意点として、 $a_{1} \gt x$ である場合には、 $a_{1} = x$ となるまで $a_{1}$ を減らす必要がある。

よって、最初の 2 要素 $a_{1}, a_{2}$ については、次のようにすればよい。

$a_{1} \gt x$ である場合には、 $a_{1} = x$ となるまで $a_{1}$ を減らす
その後、 $a_{1} + a_{2} \gt x$ である場合には、 $a_{1} + a_{2} = x$ となるまで $a_{2}$ を減らす

その後

次に $a_{2}, a_{3}$ について考える。

そうすると、同様の議論によって、 $a_{1}, a_{2}$ についての手続きをそのまま踏襲すればよいことに気づく。つまり、

$a_{2} \gt x$ である場合には、 $a_{2} = x$ となるまで $a_{2}$ を減らす (実際にはこの場合は発生しない)
$a_{2} + a_{3} \gt x$ である場合には、 $a_{2} + a_{3} = x$ となるまで $a_{3}$ を減らす

とすればよい。それ以降も $i = 3, 4, \dots, N-1$ について、 $a_{i}$ と $a_{i+1}$ に同様の処理を続けていけばよい。

全体の計算量は $O(N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, x;
    cin >> N >> x;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    
    // 左端から順に見ていく
    long long res = 0;
    for (int i = 0; i+1 < N; ++i) {
        if (a[i] + a[i+1] <= x) continue;
        
        // そもそも a[i] > x である場合には a[i] = x になるまで削る
        if (a[i] > x) {
            res += a[i] - x;
            a[i] = x;
        }
        
        // a[i] よりも a[i+1] を下げておいた方が、後にとってより良い
        long long need = a[i] + a[i+1] - x;  // a[i] <= x が保証されるので need >= 0
        res += need;
        a[i+1] -= need;
    }
    cout << res << endl;
}