自动搬运

查看原文

来自洛谷，原作者为

	YYen **

搬运于2025-08-24 22:32:25，当前版本为作者最后更新于2021-07-12 00:42:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：双指针

比赛时候看到这个题脑海闪过双指针，测试了几组例子发现都没问题，交了就AC了，说一下思路：

先约定，左指针 $i$ 初始值为 $1$ ，以及右指针 $j$。

从左往右逐个元素进行枚举，

①、如果某个元素值与下标相同，代表该元素处于正确的位置，左指针 $i$ 加 $1$ 枚举下一个元素。

②、不同则代表该元素处于不正确的位置，此时左指针 $i$ 指向的下标即为排序的左端点，因此生成右指针 $j$ ，初始化为 $i + 1$ ，开始往后查找排序的右端点。该查找过程还需要一个 $maxv$ 变量来维护双指针范围内的区间最大值，当右指针 $j$ 不停向右滑动，直至指向的下标大于等于区间最大值时，右指针 $j$ 指向的下标即为排序的右端点（这个道理应该是显然的，因为如果右指针 $j$ 指向的下标不如区间最大值 $maxv$ 大，代表还没找到区间最大值的对应位置，还需要进一步扩大区间长度，所以右指针 $j$ 还需要继续右移）。此时排序区间长度为 $j - i + 1$ 。更新左指针 $i$ 为右指针 $j$ 的下一个位置，重复以上过程，直至全部元素枚举完毕。

最终时间复杂度为 $O(n)$ 。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int a[1000005];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, ans = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        int i = 1;
        while (i <= n)
        {
            if (a[i] == i) // 相同 
                i++;
            else // 不同 
            {
                int maxv = a[i];
                int j = i + 1;
                maxv = max(maxv, a[j]);
                while (maxv > j)
                {
                    j++;
                    maxv = max(maxv, a[j]);
                }
                ans += j - i + 1;
                i = j + 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}