UVa 1125 - Sherlock Holmes

contents

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

Problem

有 N 個箱子,每個箱子都有 M 顆球,每一個箱子的黑、白球分配的個數不同,希望分成兩堆,每一堆必須有 N/2 個箱子,並且要符合黑球、或白球必須在兩堆佔有多數 (> 50%) 的情況。

假設佔有的比例分別為 m1, m2,最大化 min(m1, m2)

Sample Input

1
2
3
4
5
6
4
30
17 13
12 18
20 10
14 16

Sample Output

1
W 51.67

Solution

N 很大,M 也很大。一開始就目測需要 random 的隨機交換法,這樣湊出答案的機率是挺高的。

當然這有點不靠譜,使用 dp 背包問題,由於狀態數量太多,必須使用 set 壓縮。

dp[i][j] 表示放置前 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
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <algorithm>
using namespace std;
int main() {
int n, m, A[32767];
while (scanf("%d %d", &n, &m) == 2) {
int w, b, wsum = 0, bsum = 0;
for (int i = 0; i < n; i++) {
scanf("%d %d", &w, &b);
wsum += w, bsum += b;
A[i] = w;
}
if (wsum == bsum || n%2 != 0) {
puts("No solution");
continue;
}
char major = 'W';
if (wsum < bsum) {
major = 'B';
wsum = bsum;
for (int i = 0; i < n; i++)
A[i] = m - A[i];
}
set<int> dp[32767];
set<int>::iterator it;
dp[0].insert(0);
for (int i = 0; i < n; i++) {
int w = A[i];
for (int j = min(i, n/2 - 1); j >= 0; j--) {
for (it = dp[j].begin(); it != dp[j].end(); it++)
dp[j+1].insert((*it) + w);
}
}
int ret = -1;
int half = n/2 * m / 2;
for (it = dp[n/2].begin(); it != dp[n/2].end(); it++) {
if (*it <= wsum/2 && *it > half)
ret = max(ret, *it);
}
if (ret < 0) {
puts("No solution");
} else {
printf("%c %.2lf\n", major, ret * 100.0 / (n/2 * m));
}
}
return 0;
}