AGC Strange Sorting 题解

· · 题解

我不知道啊，他们说有思维题我就来了。

#

我们先来看操作到底在做什么。每一步操作，其实是把序列里所有的“前缀最大值”找出来，保持它们原来的顺序，整体剪切到序列的末尾。前缀最大值就是那些“从开头到现在为止的最大值刚好是自己”的位置。这个观察很重要，因为一旦一个数被确认为前缀最大值，它在当前这一步就一定会被扔到后面去。

接下来就是思维转折点。一个元素是不是前缀最大值，只取决于它前面有没有比它大的数。因此，数值较小的元素无论怎么移动，都不会影响数值较大的元素的判定。换句话说，如果我们只关心数值在某个区间内的那些元素，完全可以暂时忽略比它们都小的元素，剩下的那部分序列的高低项操作效果，和在整个序列上操作后只看这部分的结果是一样的。

这给了我们一个机会：可以把问题按数值从大到小一层一层地剥离。一开始只考虑最大的那个数 N，显然它自己不需要任何操作。然后我们逐步把 N-1, N-2, \dots, 1 加进考虑范围。每加进一个更小的数，我们就看看要不要为它付出额外的操作次数。

你可能会发现，在我们所关心的大数字集合里，它们永远不会是完全乱序的，而是处于一种“循环有序”的状态。想象把这些数字按值从小到大列出来，它们在序列里的位置正好是一个轮换顺序，比如 \textrm{pos}_4 < \textrm{pos}_5 < \textrm{pos}_6，或者 \textrm{pos}_5 < \textrm{pos}_6 < \textrm{pos}_4 这样。这种状态离完全排好序只差若干次整体循环移位。换句话说，该排序方式满足了一定的稳定性。

为了刻画当前这个循环有序结构，我们维护一个代表元素 c，一开始 c = N。当我们打算把 i 加进集合时，只需要观察三个位置：\textrm{pos}_c、\textrm{pos}_i 和 \textrm{pos}_{i+1}。如果这三个位置的大小关系恰好构成一个循环递增，比如说 \textrm{pos}_c < \textrm{pos}_i < \textrm{pos}_{i+1}，或者是 \textrm{pos}_i < \textrm{pos}_{i+1} < \textrm{pos}_c，又或者是 \textrm{pos}_{i+1} < \textrm{pos}_c < \textrm{pos}_i，那就说明 i 很自然地嵌入了现有的循环结构里，不需要增加任何操作，代表元素 c 也不用变。

反之，如果这三个位置不是循环递增的，那就意味着现在这个结构装不下 i，我们必须额外进行一次操作来重整整个集合，让它们再次进入循环有序状态。这时操作次数加一，并且把代表元素 c 更新为 i+1。因为重整之后，新的循环有序结构会以 i+1 作为最大值位置。

如果当前操作次数还是 0，也就是我们刚起步、只有 N 这一个元素，那情况退化得更简单，只看 \textrm{pos}_i 和 \textrm{pos}_{i+1} 是否满足 \textrm{pos}_i < \textrm{pos}_{i+1} 就行了，逻辑和上面是完全统一的。

于是整个算法就变得非常干净，时间复杂度 \mathcal{O}(n)，此题可解。

#include<bits/stdc++.h>
using namespace std;
int n,now,pos[200002],ans,lst;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>now, pos[now]=i;
    for(int i=n-1; i>=1; i--) {
        int cnt=(pos[lst]<pos[i])+(pos[i]<pos[i+1])+(pos[i+1]<pos[lst]);
        if(ans and cnt>=2) continue;
        if(!ans and pos[i]<pos[i+1]) continue;
        ans++,lst=i+1;
    }
    cout<<ans;
    return 0;
}