解題區/解題區 - UVa

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
*/