UVa 12861 - Help cupid

contents

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

Problem

要配對情侶,但是每一個情侶在不同的 24 時區,告知在 24 個時區的情況,希望分配兩兩一組 (先不管男女、還是男男、女女),配對花費就是兩個時區之間的差$min(|i-j|, 24 - |i-j|)$ (超過 12 小時,則會在另一個時段),求總花費最小為何?

Sample Input

1
2
3
4
5
6
6
-3 -10 -5 11 4 4
2
-6 6
8
0 0 0 0 0 0 0 0

Sample Output

1
2
3
5
12
0

Solution

首先必須知道,配對的區間不會重疊,並且盡可能與自己同一時段的人匹配。

藉此直接把同一時段的倆倆匹配,因此在每一時區要不 0 要不 1 個人。

接著窮取 24 時區的匹配花費,其一定與相鄰的匹配,窮舉一下即可。

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
#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
int n;
while (scanf("%d", &n) == 1) {
int time[24] = {}, x;
for (int i = 0; i < n; i++)
scanf("%d", &x), time[x+11]++;
for (int i = 0; i < 24; i++)
time[i] = time[i]&1;
int A[64], m = 0, ret = 0x3f3f3f3f;
for (int i = 0; i < 24; i++)
if (time[i]) A[m++] = i;
for (int i = 0; i < m; i++)
A[i + m] = A[i] + 24;
if (m == 0) ret = 0;
for (int i = 0; i < m; i++) {
int c = 0;
for (int j = 0; j < m; j += 2)
c += A[i+j+1] - A[i+j];
ret = min(ret, c);
}
printf("%d\n", ret);
}
return 0;
}
/*
6
-3 -10 -5 11 4 4
2
-6 6
8
0 0 0 0 0 0 0 0
*/