d918. 6. 雨量趨勢
標籤 :
通過比率 : 97人/115人 ( 84% ) [非即時]
評分方式:
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
輸入範例 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
輸出範例 1:
5 6 12

輸出範例2 : 
4 2 3
測資資訊:
記憶體限制: 512 MB
提示 :
標籤:
出處:
99學年度全國資訊學科能力競賽 [管理者:
Unknown User
]

本題狀況 本題討論 排行

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