题解 | #牛牛的数列#

链接：https://ac.nowcoder.com/acm/problem/13892

今天HH正在学习一种新的数据结构，叫做segment tree，经常用来解决segment问题，这里来一个： 给你一个长度为 n,(a 1，a 2 ,…, a n )的无序序列，现在你应该计算有多少段 L,R 满足两个条件： 1.段的长度为k(即R-L+1=k)。 2.L和R（都包括）之间的数字总共至少出现q次。 HH 认为这个问题太简单了，所以他把问题交给了你。

这道题目可以使用桶排加上前缀和的思路来解决(刚开始还以为是尺取法.....) 前缀和累加前n项的和,减去k项之前的前缀和就求出了区间内数字出现的总个数

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
int a[200];
int tot[400];
int sum[400];
int main() {
	int T;cin>>T;
	while(T--) {
		int n,k,q;cin>>n>>k>>q;
		int maxx=-999;
		memset(tot,0,sizeof(tot));
		memset(a,0,sizeof(a));
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			tot[a[i]]++;
			maxx=max(a[i],maxx);
		}
		sum[0]=0;
		int res=0;
		sum[1]=tot[1];
		for(int i=2;i<=maxx+k-1;i++) {
			sum[i]=sum[i-1]+tot[i];
		}
		for(int i=k;i<=maxx+k-1;i++) {
			if(sum[i]-sum[i-k]>=q) {
				res+=1;
			}
		}
		printf("%d\n",res);
	}
	return 0;
}