1062 Containers

題目連結

題目翻譯

貨櫃碼頭要把貨櫃疊成若干個堆，之後按照字母順序（A→B→C...）裝船。要求裝船時只能取每堆最頂端的貨櫃，請問最少需要幾堆才能做到？

每個貨櫃有一個大寫字母標示它要送上哪艘船。貨櫃按照輸入順序抵達，必須即時堆放。

輸入

多組測資，每行一個由大寫字母組成的字串，讀到 end 停止。

輸出

每組輸出 Case X: Y，Y 是最少堆數。

解題思路

核心規則：若貨櫃 C 放在 B 上面，則 C 的船必須比 B 更早裝（C ≤ B，字母序小的先裝）。換句話說，在一個堆裡，從底到頂字母必須非遞增（頂端最小）。

對每個新來的貨櫃 c，用 lower_bound 找第一個堆頂 ≥ c 的堆（找到第一個可以「壓在上面」的位置），把 c 放進去。若找不到就開新堆。

比較函數 return c > a.back() 讓 lower_bound 找到第一個「不滿足 c > 堆頂」的堆，也就是 c ≤ 堆頂的第一個，確保堆的非遞增性質得以維持。

這個做法類似耐心排序（Patience Sorting），最終堆數即為所求。

程式碼

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

#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

signed main() { WA();
    int t = 0;
    for (string s; cin >> s, s != "end";) { cout << "Case " << ++t << ": ";
        vector<vector<char>> v;
        for (auto &c : s) {
            auto it = lower_bound(all(v), c, [](vector<char> a, char c){
                return c > a.back();
            });
            if (it == v.end()) v.pb(vector<char>(1, {c}));
            else it->pb(c);
        }
        cout << v.size() << '\n';
    }
}