AcWing 2074：倒计数 ← 双指针算法

【题目来源】
https://www.acwing.com/problem/content/2076/

【题目描述】
艾弗里有一个由 N 个正整数构成的数组。
数组中的第 i 个整数是 Ai。
如果一个连续的子数组的长度为 m，并且按顺序包含整数 m,m−1,m−2,…,2,1，则称它为 m 倒计数。
例如，[3,2,1] 是 3 倒计数。
请帮助艾弗里计算她的数组中有多少个 K 倒计数。

【输入格式】
第一行包含整数 T，表示共有 T 组测试数据。
对于每组数据，第一行包含两个整数 N 和 K。
第二行包含 N 个整数，其中第 i 个表示 Ai。

【输出格式】
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 x 为组别编号（从 1 开始），y 为 K 倒计数的数量。

【数据范围】
1≤T≤100,
2≤K≤N,
1≤Ai≤2×10^5,
2≤N≤2×10^5

【输入样例】
3
12 3
1 2 3 7 9 3 2 1 8 3 2 1
4 2
101 100 99 98
9 6
100 7 6 5 4 3 2 1 100

【输出样例】
Case #1: 2
Case #2: 0
Case #3: 1

【样例解释】
在示例 1 中，有两个 3 倒计数，如下：
1 2 3 7 9 3 2 1 8 3 2 1
1 2 3 7 9 3 2 1 8 3 2 1
在示例 2 中，没有 2 倒计数。
在示例 3 中，有一个 6 倒计数，如下：
100 7 6 5 4 3 2 1 100

【算法分析】
● 当输入数据大于 10^5 时，使用 scanf 输入。其他情况，可用 cin 进行输入。
● 双指针算法：https://blog.csdn.net/hnjzsyjyj/article/details/140413262
（1）双指针算法，顾名思义就是使用两个指针（实践中常用两个变量来模拟双指针）来解决问题。这两个指针通常从数组/链表的两端或者一端开始移动，逐步缩小搜索范围，直到找到满足条件的解。
（2）双指针算法是一种非常实用且常见的算法技巧，在解决各种类型的问题中都有广泛应用。相比于暴力枚举法，双指针算法往往具有更优的时间复杂度。
（3）双指针算法的常见类型
在同一个序列中，用两个指针维护两个位置，或两个位置包含的区间；
在两个序列里边，两个指针指向不同的序列，来维护某种次序。
（4）双指针类型
按照指针的移动方向，双指针分为同向双指针、异向双指针。
同向双指针，也称快慢指针（两个指针一快一慢）；
异向双指针，分为对撞指针（从两边向中间移动）、背向指针（从中间向两边移动）。

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int n,m;
int q[N];

int main() {
    int T;
    scanf("%d",&T);
    for(int id=1; id<=T; id++) {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++) scanf("%d",&q[i]);
        
        int ans=0;
        for(int i=n; i>0; i--) {
            if(q[i]!=1) continue;
            int j=i-1;
            while(j>0 && q[j]==q[j+1]+1) j--;
            if(i-j>=m) ans++;
            i=j+1;
        }
        printf("Case #%d: %d\n",id,ans);
    }
    
    return 0;
}

/*
in:
3
12 3
1 2 3 7 9 3 2 1 8 3 2 1
4 2
101 100 99 98
9 6
100 7 6 5 4 3 2 1 100

out:
Case #1: 2
Case #2: 0
Case #3: 1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/140413262
https://www.acwing.com/solution/content/127812/
https://www.acwing.com/solution/content/127925/