P7714-solution

YYen · 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;
}