首页 > 试题广场 >

Segment Tree

[编程题]Segment Tree
  • 热度指数:23 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
Today HH is learning a new data structure  named segment tree, which is often used to solve segment problem, here comes one:
Gave you an unordered sequence of length n,(a1,a2,…,an), now you are supposed to calculate how many segment [L,R](1≤L≤R) are there satisfies two conditions :
1.the length of the segment is k(i.e. R−L+1=k).
2.the number between L and R(both including) appears at least q times in total. 
HH thinks the problem is too easy so he gives the problem to you.

输入描述:
The first line contains an positive integer T(1≤T≤10), represents there are T test cases. 
For each test case: The first line contains three positive integers n,k,q(1≤n≤100,1≤k≤100,1≤q≤100),the length of the sequence , the length of the segment [l,R], and the times required to appear. The second line contains n integers a1,a2…an(1≤ai≤100) - the sequence.


输出描述:
For each test case, output one line an integer : the number of segment satisfies both conditions.
示例1

输入

3
5 3 2
2 3 2 4 5
5 3 3
2 3 2 4 5
5 3 6
2 3 2 4 5

输出

4
3
0

说明

In the first example , we can find 4 segments:
[1,3],1 appears 0 time,2 appears 2 times,3 appears 1 time,so 3 times in total.
[2,4],4 times in total.[3,5] 3 times in total.[4,6],2 times in total.
In the second example, we can find:
[1,3],[2,4],[3,5].
In the third example, we can't find any.
#include<stdio.h>
#include<map>
using namespace std;
int main(){
    int T,n,i,a[105],k,q;
    //freopen("input.txt","r",stdin);
    for(scanf("%d",&T);T--;){
        map<int,int> cnt;
        scanf("%d%d%d",&n,&k,&q);
        for(i=0;i<n;i++)
            scanf("%d",a+i),cnt[a[i]]++;
        int res=0;
        for(int l=1;l<=n+10;l++){
            int r=l+k,c=0;
            for(i=l;i<r;i++) c+=cnt[i];
            if(c>=q) res++;
        }
        printf("%d\n",res);
    }
}

发表于 2017-10-26 10:50:17 回复(0)