CSES – Towers

題目連結

題意

有 N 個方塊，你要用這些方塊蓋成塔。當一個方塊疊在另一個方塊上面，上面的一定要比下面的小 (嚴格小於)。每次你可以把現在這個方塊疊在已經存在的塔上面，或是開始一個新的塔。問最少只需要幾座塔?

解題想法

這題我們最好的方法就是 greedy 的找最小的比現在方塊大的堆。這樣放的話我們才可以把比較大的留給其他更大的方塊放。而要找最小的比現在大的有沒有覺得很熟悉? 沒錯! 可以用 multiset 中的 upper_bound 來找! 我們維護一個 multiset，裡面存現在每個堆最上面的方塊是誰。這樣就可以利用 upper_bound 找可以放在哪一個。如果沒有可以放的我們就insert 一個新的堆。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <int> a(n);
    for(int &x : a) cin >> x;
    multiset <int> s;
    for(int i = 0;i < n;i++){
        auto it = s.upper_bound(a[i]);
        if(it == s.end()) { // 找不到
            s.insert(a[i]);
        } else {
            s.erase(it);
            s.insert(a[i]); 
        }
    }
    cout << s.size() << '\n';
}