小编Pib*_*ion的帖子

CSES 问题（https://cses.fi/problemset/task/2216/）。

给你一个数组，其中包含 1\xe2\x80\xa6n 之间的每个数字恰好一次。你的任务是按升序收集从 1 到 n 的数字。\n在每一轮中，你从左到右遍历数组并收集尽可能多的数字。总轮数是多少？\n约束：1\xe2\x89\xa4n\xe2\x89\xa42\xe2\x8b\x8510^5

这是我在 C++ 上的代码：

int n, res=0;\ncin>>n;\nint arr[n];\nset <int, greater <int>> lastEl;\nfor(int i=0; i<n; i++) {\n    cin>>arr[i];\n    auto it=lastEl.lower_bound(arr[i]);\n    if(it==lastEl.end()) res++;\n    else lastEl.erase(*it);\n    lastEl.insert(arr[i]);\n}\ncout<<res;\n

我遍历数组一次。如果元素 arr[i] 小于所有先前的元素，那么我“打开”一个新序列，并将该元素保存为该序列中的最后一个元素。我将已打开序列的最后一个元素存储在集合中。如果 arr[i] 小于前面的一些元素，则我采用具有最大最后一个元素（但小于 arr[i]）的现有序列，并用 arr[i] 替换该序列的最后一个元素。\遗憾的是，它仅适用于给定的三个测试中的两个测试，而对于第三个测试，输出比应有的要少得多。我究竟做错了什么？