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.
InputThe 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.
OutputAn integer n, number of ways to choose the soldiers.
Sample Input2
5 3
1 3 7 2 4
1 1000
9999
Sample Output10
1
一個簡稱CS的題目其實(shí)找到規(guī)律的話就很簡單了，一個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 閱讀(163)
評論(0) 編輯 收藏 引用