d879. 10911 - Forming Quiz teams
Tags :
Accepted rate : 97人/113人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-28 14:13

Content

你被指派一個任務要組隊參加一個猜謎比賽(MCA CPCI Quiz Championship)。有 2*N 個學生有興趣參加,而你要把他們組成 N 隊,每隊2個人。由於隊友間需要在一起練習,學生們都希望隊友的家盡可能離自己的家近一些。令 x1 代表第1隊隊員家之間的距離,x2 代表第2隊隊員家之間的距離,依此類推。你必須要確保 x1+x2+x3+...+xn 為最小。

Input

輸入含有多組測試資料。每組測試資料的第一列,有 1 個正整數 N ( N <= 8)。接下來的 2*N 列為學生的資訊。每列開始有學生的姓名,然後有學生家的座標(x,y),x,y均為介於 0 到 1000 之間的整數。學生的名字僅包含小寫英文字母,且長度最長 20。

當 N=0 時代表輸入結束,請參考Sample Input。

Output

對每一組測試資料輸出一列,輸出如題目所述的距離,就是x1+x2+x3+...+xn 最小為多少。請四捨五入到小數點後2位。輸出格式請參考Sample Output。

Sample Input #1
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
Sample Output #1
Case 1: 118.40
Case 2: 1.41
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1M
Hint :

匹配一定可以過

何不試試DP呢?

 

Tags:
出處:
UVa10911 [管理者: david942j (文旋) ]

Status Forum 排行

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