题目描述

给定一个长度为𝑛n的序列 𝑎1,𝑎2,...,𝑎𝑛a1​,a2​,...,an​ ，请问多少种方案，能够从中选取一个长度恰好为 𝑚m 的子段，且子段内所有数字的最大值不超过𝐾K？

输入格式

输入共两行：
输入第一行，三个正整数𝑛,𝑚,𝐾n,m,K
输入第二行，𝑛n个整数𝑎1,𝑎2,...,𝑎𝑛a1​,a2​,...,an​ 。

输出格式

输出一个整数，表示方案数。

数据范围

• 对于 30%30% 的数据，1≤𝑚≤𝑛≤101≤m≤n≤10
• 对于 60%60% 的数据，1≤𝑚≤𝑛≤1031≤m≤n≤103
• 对于 100%100% 的数据，1≤𝑚≤𝑛≤1051≤m≤n≤105 且−109≤𝑎𝑖,𝐾≤109−109≤ai​,K≤109

样例数据

输入:

5 2 5
3 7 2 5 1

输出:

2

说明:

选取{2,5}和{5,1}均可，共两种方案

详见代码:

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
    long long n,m,k;
    long long cnt=0;
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    long long f=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]>k)
        {
            if (f>=m)
            {
                cnt+=f-m+1;
            }
            f=0;
 
        }
        else
        {
            f++;
        }
    }
    if (f>=m)
    {
        cnt+=f-m+1;
    }
    cout<<cnt;
    return 0;
}