L2-014 列车调度

· 2022-4-15   · 次阅读   · 字数统计: 128字   · 阅读时长≈ 1分钟

  · 算法题解   · GPLT

题目链接

L2-014 列车调度

分析

求最少下降子序列数，等于求最长上升子序列的长度（Dilworth定理）

代码实现

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

set<int> s;

int main()
{
    int n, t;
    cin >> n;
    cin >> t;
    s.insert(t);
    set<int>::iterator it;
    for(int i = 0; i < n - 1; ++i)
    {
        cin >> t;
        if(*s.rbegin() > t)
        {
            it = lower_bound(s.begin(), s.end(), t);
            s.erase(it);
        }
        s.insert(t);
    }
    cout << s.size() << endl;
}