けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 048 C - Boxes and Candies (2Q, 茶色, 300 点)

とても教育的な Greedy 問題!

問題概要

 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;
}