a763. pB. Shark 的數學遊戲 - 高中生程式解題系統

內容

鯊魚(英文名字Shark)是一位從來不哭的男孩，有一天，他閒的發慌，發明了一個打發時間的數學遊戲。

規則是這樣的:

給兩個正整數 N , M ，代表有 N 個數字，我們要將他們分成 M ( M <= N ) 個區塊，使計算後出來的值最小。

遊戲怎麼玩呢? 來看看下面的例子:

當 N = 5 , M = 3 ，且輸入的五個數字分別為 0.5 , 0.4 , 0.4 , 0.3 , 0.2 ，我們要將這數列切成三份，

如果我這樣切 0.5 | 0.4 0.4 | 0.3 0.2

區段編號 1 2 3

計算方法為區段1個數 * 區段1和 + (區段1個數+區段2個數) *區段2和 + (區段1個數+區段2個數+區段3個數) *區段3和

則計算出來的結果為 [1 * 0.5] + [(1+2) * (0.4+0.4)] + [(1+2+2)*(0.3+0.2)] = 5.4

如果我這樣切 0.5 | 0.4 | 0.4 0.3 0.2

則計算出來的結果為 [1 * 0.5] + [(1+1) * (0.4)] + [(1+1+3)*(0.4+0.3+0.2)] = 5.8

Shark 想要知道可以玩出的最小值是多少

輸入說明

單筆測資輸入

每一行有兩個正整數 N , M ( M <= N )

接下來有 N 個 < 1 且 >= 0 的小數,至多小數後1位

輸出說明

輸出遊戲可玩出的最小值( 小數點後1位 )

範例輸入 #1

5 3
0.5 0.4 0.4 0.3 0.2

範例輸出 #1

5.4

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1K
不公開測資點#4 (10%): 1.0s , <1K
不公開測資點#5 (10%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <1M
不公開測資點#7 (10%): 1.0s , <1M
不公開測資點#8 (10%): 1.0s , <1M
不公開測資點#9 (10%): 1.0s , <1M

提示：

保證：20% 的測資滿足 N <= 10 , M <= 5
　　　50% 的測資滿足 N <= 100 , M <= 10
　　　80% 的測資滿足 N <= 1000 , M <= 100
　　　100% 的測資滿足 N <= 2000 , M <= 100

註：校內賽僅需通過前五筆測資即可AC！

特別感謝 stanley17112000 出題!!

2014/2/7 感謝 david942j 指出前五筆測資錯誤，已修正並重測!!

標籤:

出處:

2013 成功高中校內賽 [管理者： eddy841021 (C++?) ]

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