AtCoder Regular Contest 006 C - 積み重ね

問題文

C - 積み重ね

解法

Greedy. 重ねられるところまで重ねてあげて、無理だったら地面（？）に置く。できるだけ重ねてあげれば山の個数を最小にできる。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<30)-1
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> n;
    vector<int> w(n), a;
    rep(i, 0, n) cin >> w[i];
    rep(i, 0, n) {
        bool flag = true;       
        int dist = INF, itr = 0;
        rep(j, 0, a.size()) {
            if (a[j] >= w[i]) {
                flag = false;
                if (dist > a[j] - w[i]) {
                    dist = a[j] - w[i];
                    itr = j;
                }
            }
        }
        if (flag) a.pb(w[i]);
        else a[itr] = w[i];
    }
    cout << a.size() << endl;
    return 0;
}