UVa 1534 - Taekwondo

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

題目模型與 Zerojudge a192 接線問題 一樣。

題目背景在跆拳道選手,有兩團人馬,希望兩兩配對,體重差的絕對值總和越小越好。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2  
2 3
44.9
50.0
77.2
86.4
59.8
4 2
44.9
50.0
77.2
86.4
59.8
58.9

Sample Output

1
2
42.1 
23.8

Solution

按照以前的思路來看,維護的是前一個最後匹配到的人是誰,這樣的效率保證是 $O(N^2)$,這樣的效能已經相當快,中間運用到維護最小值的技巧,由於前 i-1 個人匹配到前 j 個人的最小值,那麼 i 匹配到 k 時,需要的是 min(dp[i-1][0 <= j < k]),邊掃描邊維護。

看到網路上有一個不錯的定義,採用失匹配幾個人,較多人數的那一方,將會有幾個人無法匹配,也因此紀錄第 i 個人時,另一團人有 j 個人沒匹配到,那麼當前第 i 個人,必然要與編號 i + j 的人匹配。

忘了提及,一定要先排序,轉換到接線問題時,交錯匹配的距離會比較長,這部分屬於貪心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;

int dp[512][512]; // dp[i-th match in A][#miss match in B]
void solve(vector<int> A, vector<int> B) {
assert(A.size() <= B.size());
int n1 = A.size(), n2 = B.size();
int diff = n2 - n1;
sort(A.begin(), A.end());
sort(B.begin(), B.end());

for (int i = 0; i < n1; i++) {
int mn = 0x3f3f3f3f;
for (int j = 0; j <= diff; j++) {
if (i == 0)
mn = 0;
else
mn = min(mn, dp[i-1][j]);
dp[i][j] = mn + abs(A[i] - B[i + j]);
}
}

int ret = 0x3f3f3f3f;
for (int i = 0; i <= diff; i++)
ret = min(ret, dp[n1-1][i]);
printf("%d.%d\n", ret/10, ret%10);
}
int main() {
int testcase;
int n1, n2, x, y;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &n1, &n2);
vector<int> A, B;
for (int i = 0; i < n1; i++) {
scanf("%d.%d", &x, &y);
A.push_back(x * 10 + y);
}
for (int i = 0; i < n2; i++) {
scanf("%d.%d", &x, &y);
B.push_back(x * 10 + y);
}

if (n1 < n2)
solve(A, B);
else
solve(B, A);
}
return 0;
}