从左到右遍历数组并收集尽可能多的数字

Question

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

\n

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

\n

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

\n

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

\n

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

\n

Answer 1

让我详细解释一下我的思考过程，以便您下次遇到相同类型的问题时更容易。

首先，我在面对这类问题时经常犯的一个错误就是急于模拟这个过程。问题陈述中提到的“模拟过程”是什么意思？该问题提到，进行一轮以最大化按一定顺序增加的数字的集合。所以，你从 开始1，找到它并看到下一个数字2不超出它，即2不能与 处于同一轮1并形成递增序列。因此，我们需要另一轮2。现在我们发现，2两者3都可以在同一轮中收集，因为我们从左到右移动并按递增顺序获取数字。但我们不能接受，4因为它早于 开始2。最后，4我们5需要另一轮。这样总共就进行了三轮。

现在，如果你用这种方式模拟这个过程，问题就变得很容易解决。在第一轮中，您寻找形成以 开头的递增序列的数字1。您在开始第二轮之前删除这些数字。你继续这样，直到你用完所有的数字。

但是模拟这个过程会导致时间复杂度无法通过问题陈述中提到的约束。因此，我们需要找出另一种方法，在不模拟整个过程的情况下提供相同的输出。

请注意，数字的位置在这里至关重要。为什么我们还需要另一轮2？因为它在之前1。我们不需要另一轮，3因为它发生在 之后2。同样，我们需要另一轮 for4因为它出现在 之前2。

因此，在考虑每个数字时，我们只需要关心顺序中位于其之前的数字的位置。在考虑的时候2，我们看的是1？是1在之前还是之后2？如果它来了，我们就不需要另一轮了。但如果它提前到来，我们就需要额外一轮。对于每个数字，我们都会查看此条件并在必要时增加轮数。这样，我们就可以算出总轮数，而无需模拟整个过程。

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector <int> v(n + 1), pos(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        pos[v[i]] = i;
    }
    int total_rounds = 1; // we'll always need at least one round because the input sequence will never be empty
    for(int i = 2; i <= n; ++i){
        if(pos[i] < pos[i - 1]) total_rounds++;
    }
    cout << total_rounds << '\n';
    return 0;
}

下次当您遇到此类问题时，请暂停一会儿，并尝试控制用代码模拟该过程的冲动。几乎可以肯定，一些巧妙的观察将使您获得最佳解决方案。