contents
Problem
要配對情侶,但是每一個情侶在不同的 24 時區,告知在 24 個時區的情況,希望分配兩兩一組 (先不管男女、還是男男、女女),配對花費就是兩個時區之間的差 $min(| i-j|, 24 - |i-j|)$ (超過 12 小時,則會在另一個時段),求總花費最小為何?
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
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("%dn", ret); } return 0; } 6 -3 -10 -5 11 4 4 2 -6 6 8 0 0 0 0 0 0 0 0 */
|
近期评论