你被指派一個任務要組隊參加一個猜謎比賽(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呢?
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|