题目描述

今天，HH正在学习一种名为分段树的新数据结构，它通常用于解决分段问题，这里有一个： 给你一个长度为n的无序序列，（a1一个2,...,an），现在你应该计算有多少段[L，R]（1≤L≤R）满足两个条件： 1.段的长度为 k（即 R−L+1=k）。 2.L和R之间的数字（包括）总共至少出现q次。 HH认为问题太容易了，所以他把问题告诉你。

using namespace std;
int a[102],cnt[102];
int main() {
	int t;
	cin>>t;
	while(t--){
		int n,k,q,count=0;
		cin>>n>>k>>q;
		memset(cnt,0,sizeof(cnt));//每轮都要初始化为0 
		for(int i=1;i<=n;i++){
			cin>>a[i];
			cnt[a[i]]++;//用桶排序的思想,把数据装进去，每次装入一个数据，桶就加一
		}
		for(int i=1;i<=100+1-k;i++)//R-L+1=k;i的最大是i=100+1-k;
		{
			int num=0;
			for(int j=i;j<=k-1+i;j++){//因为R-L+1=K;所以R最大是R=k-1+i;
			num+=cnt[j];
			}
			if(num>=q){
				count++;
			}
		}
		cout<<count<<endl;
	}
	return 0;
}