d918: 6. 雨量趨勢
標籤 :
通過比率 : 85% (82 人 / 97 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2010-12-24 09:27

內容

  台灣近年來經常豪雨成災。每遇有豪雨,新聞記者就將以往降雨紀錄拿出,並以聳動字眼云之,如「30 年來最大降雨量」、「40 年來首見」等。李先生是一位科學家,認為用直覺讀取數據容易造成偏頗,他想用更科學的方式來解讀降雨量,希望能找出降雨量長期趨勢。在觀察一連串的降雨量數據後,李先生想找出最長的遞增序列,以代表長期趨勢。在他所找到的長期趨勢資料中,一般而言是逐步上升,但某次破紀錄的最大雨量之後,若有稍大雨量 (雖未破紀錄),亦視為遞增序列之內容。換言之,他欲找出最長近乎遞增序列。
舉例來說,李先生的雨量數據有12 個,如下:'
    9, 15, 3, 14, 14, 8, 10, 11, 17, 15, 14, 13
另外設定一個 E 值,代表稍大雨量與長期趨勢目前最大雨量可以允許的差值。假設 E = 1,則可以找出下列五組最長近乎遞增序列,其長度均為
6 :
(9, 15, 14, 14, 15, 14), (9, 8, 10, 11, 15, 14), (3, 8, 10, 11, 15, 14), (9, 8, 10, 11, 14, 13), (3, 8, 10, 11, 14, 13)
又若 E = 0,則最長近乎遞增序列有四組 (3, 8, 10, 11, 13), (3, 8, 10, 11, 14), (3, 8, 10, 11, 15), (3, 8, 10, 11, 17),其長度均為 5

  再看另一個例子,假設雨量數據為 3, 4, 4, 6, 5, 4。若 E = 0,則有三組最長近乎遞增序列:(3, 4, 4, 6) , (3, 4, 4, 5), (3, 4, 4, 4),長度均為 4。若 E =  l,則有二組:(3, 4, 4, 6, 5), (3, 4, 4, 5, 4)。若 E = 2,則有一組:(3, 4, 4, 6, 5, 4)。本題的答案只要輸出長度即可。

輸入說明
  輸入檔分成三部分,首先第一行有兩個正整數 n m ,其中 l <= n <= 3500, 1 <= m <= 3;第二行有 n 個雨量數據;第三行有 m E 值。雨量與 E 值均為非負整數,最大值不超過 999999 。每一行的數字與數字問會以空白隔開。
輸出說明
分別輸出 m E 值所對應的最長近乎遞增序列之長度。這 m 個整數請輸出於一列,且相鄰兩個整數之間以一個空白隔開。
範例輸入
輸入範例 1:
12 3
9 15 3 14 14 8 10 11 17 15 14 13 
0 1 999990

輸入範例 2: 
4 3
1 0 999900 999800
1000 0 l 
範例輸出
輸出範例 1:
5 6 12

輸出範例2 : 
4 2 3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
提示 :
標籤:
出處:
99學年度全國資訊學科能力競賽 [編輯:
pcshic (PCSHIC)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」