Problem : 342 - pF.區間均值優化問題

Problem Statistics

Solved Member: 27　　Submission: 89　　User Tried: 38

Statement:

法國資料科學家Fûjun Dïansuan於西元1992年為區間均值優化問題提出了一系列的演算法(segment-avg optimize algorithms)，其演算法核心針對1974年MLDM(Machine Learning and Data Mining)年會，由Shiautsz&nushen(網名)提出的最大區間平均值問題(Maximum seg-avg problem)提出的解法有跨世紀的進展。這個問題是這樣描述的：
對於一維的資料上，存不存在一個連續區間X[left, right]，其區間平均值大於等於給定的K
慶祝此題問世40週年，出題者想請你寫一個程式解決這個問題。

Input:Output:

第一行有一個正整數 T ，代表接下來有 T 筆測試資料。
每筆測試資料有兩行，第一行有兩個正整數 N, K，表示資料長度與希望達到的平均值K 第二行有N個正整數Xi，表示題目給定的一維資料

每筆測試資料一行，如果存在請輸出 "Yes"(不含引號) ，不存在則輸出 "No"(不含引號)。

Sample Input:Sample Output:

2
4 4
1 6 4 6
2 100
71 22

Yes
No

HINT:

占總分20%的資料滿足 $1\le N\le 10$
占總分80%的資料滿足 $1\le N\le 1,500$
占總分100%的資料滿足 $1\le N\le 100,000$
全部的資料滿足$0\le K\le 2,147,483,647$

連續區間X[left, right]定義 : ${ X }_{ left },{ X }_{ left+1 }...{ X }_{ right }$
連續區間X[left, right]長度 : $1\le right-left+1\le N$

Source:

103附中校內賽

Problem Setter

rilak

Testdata:

Test	Time	Memory	Score
0	2000ms	262144kb
1	2000ms	262144kb	10
2	2000ms	262144kb	10
3	2000ms	262144kb	10
4	2000ms	262144kb	10
5	2000ms	262144kb	10
6	2000ms	262144kb	10
7	2000ms	262144kb	10
8	2000ms	262144kb	10
9	2000ms	262144kb	10
10	2000ms	262144kb	10