事情發生在吉士解完古墓中所有的方塊之後,在所有方塊都被解開的瞬間,出現在吉士面前的是神秘的古文。
同一時間,源 達博所開挖的秘密隧道也通到吉士的所在地,而吉士正研究著牆上的古文。
此時吉士口中正說道:「這難不成是東方的古文嗎?」
源 達博問:「東方的古文是什麼?」
吉士回答:「據說東方的古文記載了獲得東方神秘力量的方法,如果擁有這個力量的話可以成為新世界的神。咦?你是什麼人啊!」
這整座古墓從頭到尾就非常神祕,有神秘的棺木、神秘的方塊、神秘的碑文還有神秘的大洞(?),源 達博看著牆面上的古文,心想:「如果能夠解開這個古墓裡種種神秘的謎團,獲得東方神秘力量,說不定就能夠重振家業了!」,為了了解這段古文在記錄些什麼,源 達博打算和吉士合作解決這些謎團,但是由於古文實在是太長一篇了,於是源 達博找了$M$位朋友來一起幫忙抄這些古文。
由於要確切記錄各個古文字出現的順序,所以每個人只能抄寫一段連續的文字,不能跳著抄寫。源 達博現在已經安排好了一個抄寫方案,決定好了每個人該負責抄寫哪個部分,但此時吉士卻說:「每個古文字的寫法難度不同啊!如果分配不當的話會導致某些人的工作量太大。」
吉士大約瀏覽過所有古文之後,寫下了一份抄寫每個古文所需要花的時間,交給了源 達博,源 達博為求公平起見決定讓這$M$個人每個人的工作量都不能超過某個上限$X$,但同時這$M$個人也必須把所有的古文字都抄寫完才算達成任務。糟糕的是,現在源 達博身上沒有帶著筆電,沒有辦法馬上寫個程式計算,身為源 達博朋友的你,打算幫他寫個程式計算如何分配,可以讓$X$值盡量小。
輸入的第一列有一個正整數$T (T \leq 50)$,代表以下有幾組測試資料。
接下來每組測試資料包含兩行,第一行有兩個整數$N,M(1\leq N,M \leq 10^5)$,代表依序要抄$N$個古文字,有$M$個人可以抄寫。
測試資料的第二行包含$N$個整數,以空白隔開,代表抄每個文字所需要花費的工作量($C_i$)。
對於每筆測試資料輸出工作量上限$X$的最小值。
第一筆範例輸入中,一個工作量上限$5$的抄寫方案為,一個人抄一個古文字。
1 / 2 / 3 / 4 / 5
第二筆範例輸入中,一個工作量上限$6$的抄寫方案為,第一個人抄寫前三個古文字,剩下兩人一人抄一個古文字。
1 2 3 / 4 / 5
NEOJ Problem 73
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~3 | $1\leq M\leq N\leq 20$, $1\leq C_i\leq 100$ | 40 |
2 | 0~5 | $1\leq M\leq N\leq 200$, $1\leq C_i\leq 100$ | 20 |
3 | 0~7 | $1\leq M\leq N\leq 400$, $1\leq C_i\leq 10000$ | 20 |
4 | 0~9 | 無額外限制 | 20 |