解題區/解題區 - UVa

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;
}