题目描述
给定一个长度为𝑛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;
}