题目描述

艾弗里有一个由N个正整数构成的数组。

数组中的第i个整数是$ A_i $。

如果一个连续的子数组的长度为m，并且按顺序包含整数m,m−1,m−2,…,2,1，则称它为 m 倒计数。

例如，[3,2,1]是3倒计数。

请帮助艾弗里计算她的数组中有多少个 K倒计数。

输入格式

第一行包含整数T，表示共有 T组测试数据。

对于每组数据，第一行包含两个整数N和K。

第二行包含N个整数，其中第i个表示 $A_i$。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为Case #x: y，其中 x为组别编号（从 1 开始），y为 K倒计数的数量。

数据范围

$ 1≤T≤100 $ ,
$ 2≤K≤N $,
$ 1≤A_i≤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

(暴力枚举) $O(nk)$

• 枚举以每个点为初始点的k个数会不会是所要求的倒计数。

• 可采用的剪枝为枚举该点是否为k和区间末尾点是否为1。

时间复杂度

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;

const int N = 2e5 + 10;

int n, k;
int a[N];

int main()
{
    int T;
    cin >> T;
    int p = 1;
    while(T--){
        cin >> n >> k;

        for(int i = 0; i < n; i++) cin >> a[i];
        int res = 0;
        for(int i = 0; i < n; i++){
            if(a[i] != k) continue;
            else{
                if(a[i + k - 1] != 1) continue;
                int cnt = 1;
                for(int j = i; j < n && j < i + k - 1; j ++){
                    if(a[j] == a[j + 1] + 1) cnt ++;
                }
                if(cnt == k) res ++;
            }
        }

        printf("Case #%d: %d\n", p++, res);
    }
    return 0;
}