你被指派一個任務要組隊參加一個猜謎比賽（MCA CPCI Quiz Championship）。有 2*N 個學生有興趣參加，而你要把他們組成 N 隊，每隊2個人。由於隊友間需要在一起練習，學生們都希望隊友的家盡可能離自己的家近一些。令 x1 代表第1隊隊員家之間的距離，x2 代表第2隊隊員家之間的距離，依此類推。你必須要確保 x1+x2+x3+...+xn 為最小。
輸入含有多組測試資料。每組測試資料的第一列，有 1 個正整數 N （ N <= 8）。接下來的 2*N 列為學生的資訊。每列開始有學生的姓名，然後有學生家的座標（x,y），x,y均為介於 0 到 1000 之間的整數。學生的名字僅包含小寫英文字母，且長度最長 20。
當 N=0 時代表輸入結束，請參考Sample Input。
對每一組測試資料輸出一列，輸出如題目所述的距離，就是x1+x2+x3+...+xn 最小為多少。請四捨五入到小數點後2位。輸出格式請參考Sample Output。
5 sohel 10 10 mahmud 20 10 sanny 5 5 prince 1 1 per 120 3 mf 6 6 kugel 50 60 joey 3 24 limon 6 9 manzoor 0 0 1 derek 9 9 jimmy 10 10 0
Case 1: 118.40 Case 2: 1.41
匹配一定可以過
何不試試DP呢?
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||