回分類題庫
h129: G.胖胖天大大薯II
關鍵字: NPSC 2013 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 19 Times / 16 Users | Submit : 85 Times / 28 Users | Accepted rate : 57%
題目加入時間 : 2014-09-16 09:42

Content: 简体中文

胖胖天為了達成他天天胖的野望,每天都以吃垮胖胖天國的麥當當為目標生活著。吃著吃著竟發現驚人的事實——胖胖天國內的麥當當同一天裡大薯的量是固定的!也就是說,同一天裡無論早晚拿到的一包大薯裡面的薯條根數都一樣,真是辛苦店員了。

為免釀成一天吃一百包大薯的悲劇,胖胖天決定一天最多只買一次大薯,但是他可以選擇在正常時段升級套餐吃一包大薯,或者利用晚上十點後買大送大的優惠一天吃兩包大薯,又或者他可以選擇那天就颯爽不吃大薯,就算點套餐也要把薯條換成玉米濃湯(他才不吃中薯小薯什麼的,一口就沒了太小家子氣了)。

隨著時間過去,胖胖天覺得大薯的量變少實在太不開心了!因此,如果胖胖天某天吃了 X 根薯條,那從此以後如果有吃薯條的話,該天至少也要吃 X 根薯條。

好心的正妹店員湯湯偷偷透露了接下來 N 天麥當當的一包大薯有幾根薯條給胖胖天知道。已知聰明的胖胖天會吃儘量多天的大薯,且上次吃薯條時該天吃了 M 根,請問他最多在接下來 N 天中可以吃到幾天大薯呢? 

Input:

輸入的第一行有一個正整數 T (T ≤ 1000),代表測試資料的組數。

每一組測試資料有兩行。第一行有兩個正整數 N, M (N ≤ 100000, M ≤ 109),中間以一個空白隔開。

第二行包含了 N 個正整數 Ci (Ci ≤ 109) ,中間各以一個空白隔開,代表接下來第 i 天時一包大薯會有 Ci 根。

保證至少 99% 的測試資料中 N ≤ 1000。 

Output:

對於每一筆測試資料請輸出一行,包含一個整數表示胖胖天在接下來 N 天中最多可以吃幾天
大薯。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
3 1
1 1 1
3 1
1 2 3
3 1
1 3 2
3 3
5 1 4

Sample Output :

3
3
3
2

Hint :

[註腳]

  1. 胖胖天國的麥當當使用須彌芥子袋來裝大薯,不必擔心裝不下的問題。
  2. 「我可是靈活的胖子」胖胖天道。 

 

Author :

NPSC 2013 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum