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

Question

CSES 问题 (https://cses.fi/problemset/task/2216/)。

给你一个数组，其中包含 1…n 之间的每个数字恰好一次。你的任务是按升序收集从 1 到 n 的数字。在每一轮中，您从左到右遍历数组并收集尽可能多的数字。总轮数是多少？约束条件：1≤n≤2⋅10^5

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

int n, res=0;
cin>>n;
int arr[n];
set <int, greater <int>> lastEl;
for(int i=0; i<n; i++) {
    cin>>arr[i];
    auto it=lastEl.lower_bound(arr[i]);
    if(it==lastEl.end()) res++;
    else lastEl.erase(*it);
    lastEl.insert(arr[i]);
}
cout<<res;

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

Answer 1

我把我的思考过程详细说一下，这样下次遇到同类问题的时候会更容易。

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

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

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

注意数字的位置在这里很重要。为什么 2 还需要一轮？因为它在 1 之前。我们不需要 3 的另一轮，因为它在 2 之后。同样，我们需要另一轮 4 因为它在 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;
}

下次遇到此类问题时，暂停一下，尽量控制自己用代码模拟该过程的冲动。几乎可以肯定，会有一些巧妙的观察可以让您获得最佳解决方案。

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

Go through the array from left to right and collect as many numbers as possible

c++

sorting

algorithm

sequence