posts - 74,  comments - 33,  trackbacks - 0

TimeLimit : 1 Second   Memorylimit : 32 Megabyte  

Totalsubmit : 590   Accepted : 131

Anti-terrorism is becoming more and more serious nowadays. The country now has n soldiers,and every solider has a score.

We want to choose some soldiers to fulfill an urgent task. The soldiers chosen must be adjacent to each other in order to make sure that they can cooperate well. And all the soldiers chosen must have an average score greater than a.

Now, please calculate how many ways can the chief of staff choose the soldiers.

Input

The first line consists of a single integer t, indicating number of test cases.

For each test case, the first line gives n, the number of soldiers, and a, the minimum possible average score(n<=100000,a<=10000). The second line gives n integers, corresponding to the soldiers' scores in order. All the scores are no greater than 10000.

Output

An integer n, number of ways to choose the soldiers.

Sample Input

2
5 3
1 3 7 2 4
1 1000
9999

Sample Output

10
1
一个简称CS的题目其实找到规律的话就很简单了,一个Mergersort就能AC;
Mergersort代码如下:
void Mergersort(INT l,INT r){
    INT i,j,sign;
    
if(l>=r)return ;
    INT mid
=(l+r)>>1;
    Mergersort(l,mid);
    Mergersort(mid
+1,r);
    sign
=l,i=l,j=mid+1;
    
while(i<=mid&&j<=r){
        
if(score[j]>score[i]){
            all
+=mid-i+1;
            now[sign
++]=score[j++];    
        }

        
else now[sign++]=score[i++];        
    }

    
while(i<=mid)now[sign++]=score[i++];
    
while(j<=r)now[sign++]=score[j++];
    
for(i=l;i<=r;i++)
        score[i]
=now[i];
    
return ;
}
posted on 2009-02-21 20:13 KNIGHT 阅读(152) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年1月>
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜