[AtCoder] ARC 006 C – 積み重ね

2020年10月13日2020年12月12日

問題

方針

山 \( i \) に積まれている一番上の重さを \( v_i \) とします。初期値は、\( v_1 = w_1 \) です。段ボール \( j \) が全ての山に対して \( v_i < w_j \) を満たすとき、新しい山を作ります。そうではないとき、\( v_i \geq w_j \) を満たす \( i \) に対して、\( v_i – w_j \) を最小化する山を見つけます。そして、\( v_i \leftarrow w_j \) と更新します。

段ボール \( i \) を載せられる山があるにもかかわらず、新しく山を作る方法がなぜダメかというと、コスト \( 1 \) 増えるのと同時に、許容量が \( w_i \) の山が新たにできます。新しく山を作らなければ、コストが増えずに、許容量が \( w_i \) の山ができます。

コード

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

int main() {
    int N;
    cin >> N;
    int w[N];
    for (int i = 0; i < N; i++) {
        cin >> w[i];
    }
    vector<int> v;
    v.push_back(w[0]);
    for (int i = 1; i < N; i++) {
        int idx = -1;
        for (int j = 0; j < v.size(); j++) {
            if (w[i] <= v[j]) {
                if (idx == -1) idx = j;
                else {
                    if (v[idx] > v[j]) idx = j;
                }
            }
        }
        if (idx == -1) {
            v.push_back(w[i]);
        } else {
            v[idx] = w[i];
        }
    }
    cout << v.size() << "\n";
    return 0;
}