首页 > itarticle > uva 1534 – taekwondo

uva 1534 – taekwondo

admin 11月 11, 2020 0

contents

Problem

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

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

Sample Input

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 的人匹配。

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

#include <stdio.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
int dp[512][512]; 
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.%dn", 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;
}