e197: 倒回收
Tags :
Accepted rate : 19人/20人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-05-26 14:31

Content

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

 

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

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

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

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

Input

輸入首行有一個正整數$\color{black}{\space T(T\leq 10)\space}$,代表測資筆數。

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

接下來一行有$\color{black}{\space M\space}$個兩兩相異的正整數$\color{black}{\space d_1\sim d_M(d_i\leq 10^9)\space}$以空格隔開。

最後一行有$\color{black}{\space M\space}$個正整數$\color{black}{\space c_1\sim c_M(1\leq c_i\leq 10^4)\space}$,代表第$\color{black}{\space i\space}$種回收的回收籃共有$\color{black}{\space c_i\space}$籃。

Output

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

Sample Input
2
3 3
3 2 1
2 2 2
1 5
1 5 4 3 2
2 1 1 1 2
Sample Output
12
22
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (16%): 1.0s , <1K
不公開 測資點#1 (29%): 1.0s , <1M
不公開 測資點#2 (23%): 1.0s , <10M
不公開 測資點#3 (32%): 1.0s , <10M
Hint :

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

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

 

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

測資點$\color{black}{\space 0(16\%)\space}$:$\color{black}{\space M=2\space}$。

測資點$\color{black}{\space 1(29\%)\space}$:$\color{black}{\space M\leq 1000\space}$。

測資點$\color{black}{\space 2(23\%)\space}$:$\color{black}{\space c_i=1\space}$。

測資點$\color{black}{\space 3(32\%)\space}$:無特別限制。

Tags:
出處:
板橋高中校友盃 [管理者:
baluteshih (波路特石)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」