L2-014 列车调度

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n, t;
    cin >> n;
    
    // 使用 set 自动维护所有队列的队尾（从小到大排序）
    // 初始化 set，放入 0 作为哨兵（保证 set 非空，且所有车号都 > 0）
    set<int> s;
    s.insert(0);
    
    for (int i = 0; i < n; i++) {
        cin >> t;
        
        // 分析：当前车号 t 需要插入队列
        // 条件：如果 t < 当前所有队列队尾的最大值（即 s 的最后一个元素）
        // 为什么？因为队列要求：队尾必须 > t（才能保证 t 能插入队尾）
        if (t < *s.rbegin()) {
            // 选择最接近 t 的队尾（即第一个大于 t 的队尾值）
            // s.upper_bound(t) 返回第一个大于 t 的迭代器位置
            // *s.upper_bound(t) 取出该位置的值（即要替换的队尾）
            s.erase(*(s.upper_bound(t)));
        }
        
        // 无论是否删除，都要将 t 插入 set（作为新的队尾）
        s.insert(t);
    }
    
    // 结果：s.size() 包含哨兵 0，所以实际队列数 = s.size() - 1
    cout << s.size() - 1;
    return 0;
}

import bisect

def main():
    n = int(input().strip())
    # 使用列表 tails 维护所有队列的队尾（从小到大排序）
    # 初始化 tails，放入 0 作为哨兵（保证非空，且所有车号 > 0）
    tails = [0]
    
    for _ in range(n):
        t = int(input().strip())
        
        # 分析：当前车号 t 需要插入队列
        # 条件：如果 t >= tails 最后一个元素（即当前所有队列队尾的最大值）
        # 为什么？因为队尾必须 > t 才能插入，如果 t 更大则不能插入已有队列
        if t >= tails[-1]:
            # 新开一条队列：将 t 添加到 tails 末尾
            tails.append(t)
        else:
            # 找到第一个大于 t 的位置（即最接近 t 的队尾）
            # bisect.bisect_right(tails, t) 返回插入位置（第一个大于 t 的索引）
            pos = bisect.bisect_right(tails, t)
            # 替换该位置的值为 t（表示 t 成为该队列的新队尾）
            tails[pos] = t
    
    # 结果：tails 包含哨兵 0，所以实际队列数 = len(tails) - 1
    print(len(tails) - 1)

if __name__ == '__main__':
    main()