e197. 倒回收 - 高中生程式解題系統

內容

時間堆起了塵埃人海之中習慣混亂
不用感到困難改變本來不簡單
教室走廊黑板我曾讓它一塵不染
時間堆起了塵埃人來人往髒亂太快
這麼做太不該這生活需要我的愛
別囉嗦別囉嗦一起走
......

　　板橋高中在某年開始，打掃時間一到，名為「Clean up」的打掃歌就會響起，學生們就會知道需要打掃了。

　　這次，所有倒回收的 $N$ 個學生們集結了起來，討論了起來，如果假設每個人可以無延遲的拿到任何一個回收籃，且在每個人一趟最多只能拿兩個回收籃的情況下，要如何最高效的把回收倒完呢？

　　板橋高中倒回收的地點非常地擁擠，已知所有 $M$ 種回收的分類都排成一直線，且每一種回收距離回收場入口的距離是 $d_{1} \sim d_{M}$ ，假設一次只能有一個人進去把手上的回收倒完，出來之後另一個人才能進去，那一個進去的人手上若拿著兩種回收籃分別是 $a, b$ ，則他需要走 $max (d_{a}, d_{b}) \times 2$ 的距離才有可能把回收倒完(走過去到最遠的那桶再走回來，中途遇到另一桶就可以倒了另一籃了)。

　　現在有很多籃回收籃(見輸入說明)要分給這 $N$ 個學生倒，假設每個學生走路速度一樣，請問在最佳的分配下(每個人可以不只倒一次回收)，學生們最少需要走的總距離和(等價於最佳效率)為多少？

輸入說明

輸入首行有一個正整數 $T (T \leq 10)$ ，代表測資筆數。

每筆測資首行有兩個正整數 $N, M (N \leq 1000, M \leq 10^{5}))$ 如題目所述。

接下來一行有 $M$ 個兩兩相異的正整數 $d_{1} \sim d_{M} (d_{i} \leq 10^{9})$ 以空格隔開。

最後一行有 $M$ 個正整數 $c_{1} \sim c_{M} (1 \leq c_{i} \leq 10^{4})$ ，代表第 $i$ 種回收的回收籃共有 $c_{i}$ 籃。

輸出說明

輸出學生們最少需要走的總距離和為多少。

範例輸入 #1

範例輸出 #1

12
22

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (16%): 1.0s , <1K
不公開測資點#1 (29%): 1.0s , <1M
不公開測資點#2 (23%): 1.0s , <10M
不公開測資點#3 (32%): 1.0s , <10M

提示：

　　範例輸入中，第一筆測資最好的分配方式是讓第一個人倒最遠的兩籃、第二個人倒次遠的兩籃、第三個人倒最近的兩籃，這樣的總距離和為 $3 \times 2 + 2 \times 2 + 1 \times 2 = 12$ 。

　　第二筆測資雖然只有一個人，但他還是可以來回跑好幾趟，最佳的分配方式為，第一趟倒距離 $5, 4$ 的各一籃；第二趟倒距離 $3, 2$ 的各一籃；第三趟倒距離 $2, 1$ 的各一籃；第四趟倒距離 $1$ 的最後一籃，這樣的總距離和為 $5 \times 2 + 3 \times 2 + 2 \times 2 + 1 \times 2 = 22$ 。

　　本題共有四組測試題組，條件限制如下所示。每一組可對應到一或多筆測試資料。

測資點 $0 (16 %)$ ： $M = 2$ 。

測資點 $1 (29 %)$ ： $M \leq 1000$ 。

測資點 $2 (23 %)$ ： $c_{i} = 1$ 。

測資點 $3 (32 %)$ ：無特別限制。

標籤:

出處:

板橋高中校友盃 [管理者： baluteshih (波路特石) ]

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