称球问题扩展——根据当前已知信息选择最优称量方案

似乎是某个TopCoder SRM的题目。

N 个球,有一个是坏的,坏球重量与好球不同(略轻/重于好球)。有一个天平,可以告知左右两边孰重孰轻,最小化最坏情况下称量次数,给出称量方案。下面讨论该问题的一个扩展——如何通过已知信息(即之前称量结果,之前的称量结果可能不是最优的)选择下一步称量方案,最小化最坏情况下的称量次数。

根据已有信息把所有球分为4类: - 肯定是好球 - 不可能比好球轻(不能确定是否为坏球) - 不可能比好球重(不能确定是否为坏球) - 不知道任何信息

每个球必定属于以上四类中的某一类。我们只需知道每一类的数目即可,具体编号无关紧要。令\(s[nh][nl][nu]\)表示有\(nh\)个1类球,nl 个2类球,nu 个3类球,最坏情况下需要称量的次数。枚举一边放置的各类型球数 lh(1类),ll(2类),lu(3类),枚举另一边放置的各类型球数 rh(1类),rl(2类),ru(3类),re(0类)。如果两边都有0类球,那么我们可以在两边各移去一个。我们可以保证0类球只出现在一边,不妨设为 rh(1类),rl(2类),ru(3类) 一边。

1
2
3
4
5
s[nh][nl][nu] = max(
s[lh+lu][rl+ru][0]+1, #lh,ll,lu一边重于rh,rl,ru,re一边
s[rh+ru][ll+lu][0]+1, #lh,ll,lu一边轻于rh,rl,ru,re一边
s[nh-lh-rh][nl-ll-rl][nu-lu-ru]+1, #一样重
)

下面程序应用到了 C++0x 的 multi-declarator auto,该特性已经被 GCC 4.4 实现。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <algorithm>
#include <climits>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> vi;

const int N = 81;
int n, mem[N][N][N];
basic_string<int> res, se, sh, sl, su;

int compute(int ne, int nh, int nl, int nu, bool flag)
{
if (ne == n || nh+nl == 1 && ne == n-1)
return 0;
int &ret = mem[nh][nl][nu];
if (ret) return ret;
ret = INT_MAX/2;
for (int lh = 0; lh <= nh; ++lh)
for (int ll = 0; ll <= nl; ++ll)
for (int lu = 0; lu <= nu && lh+ll+lu <= n/2; ++lu)
for (int rh = 0; rh <= nh-lh; ++rh)
for (int rl = 0; rl <= nl-ll; ++rl)
for (int ru = 0; ru <= nu-lu; ++ru)
if (lh+ll+lu >= rh+rl+ru)
{
int re = lh+ll+lu-rh-rl-ru;
if (re > ne) continue;
int t = max(max(
compute(n-lh-lu-rl-ru, lh+lu, rl+ru, 0, false)+1,
compute(n-rh-ru-ll-lu, rh+ru, ll+lu, 0, false)+1),
compute(ne+lh+ll+lu+rh+rl+ru, nh-lh-rh, nl-ll-rl, nu-lu-ru, false)+1);
if (flag && t < ret)
{
basic_string<int> s1 = sh.substr(0, lh)+sl.substr(0, ll)+su.substr(0, lu),
s2 = sh.substr(lh, rh)+sl.substr(ll, rl)+su.substr(lu, ru)+se.substr(0, re);
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
res = s1;
res.push_back(-1);
res += s2;
}
ret = min(ret, t);
}
return ret;
}

bool solve(vector<vi> left, vector<vi> right, string result)
{
vi p(n, 3);
for (int i = 0; i < left.size(); ++i)
if (result[i] == 'E')
{
for (auto it = left[i].begin(); it != left[i].end(); ++it)
p[*it] = 0;
for (auto it = right[i].begin(); it != right[i].end(); ++it)
p[*it] = 0;
}
else
{
if (result[i] == 'R') left[i].swap(right[i]);
for (auto it = left[i].begin(); it != left[i].end(); ++it)
p[*it] &= ~2;
for (auto it = right[i].begin(); it != right[i].end(); ++it)
p[*it] &= ~1;
for (int j = 0; j < n; ++j)
if (find(left[i].begin(), left[i].end(), j) == left[i].end()
&& find(right[i].begin(), right[i].end(), j) == right[i].end())
p[j] = 0;
}
for (int i = 0; i < n; ++i)
switch (p[i])
{
case 0: se.push_back(i); break;
case 1: sh.push_back(i); break;
case 2: sl.push_back(i); break;
case 3: su.push_back(i);
}
if (se.size() == n) return false;
compute(se.size(), sh.size(), sl.size(), su.size(), true);
return true;
}

int main()
{
int m;
string result;
vector<vi> left, right;

cin >> n >> m;
while (m--)
{
char op;
int num, x;
vi L, R;
cin >> num;
for (int i = 0; i < num; ++i)
cin >> x, L.push_back(x);
for (int i = 0; i < num; ++i)
cin >> x, R.push_back(x);
while (isspace(cin.peek())) cin.ignore();
cin >> op;
result += op;
left.push_back(L);
right.push_back(R);
}

if (!solve(left, right, result))
cerr << "error\n";
else if (!res.empty())
{
auto it = find(res.begin(), res.end(), -1);
copy(res.begin(), it, ostream_iterator<int>(cout, " "));
cout << "- ";
copy(it+1, res.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
return 0;
}

输入格式: 两个整数 n,m,分别表示球的数量和已经称量的次数 之后 m 行,每一行第一个数 t,之后是 t 个数 a[0...t-1],代表天平左边各个球的编号,然后又是 t 个数 b[0...t-1],代表天平右边各个球的编号,接着是一个字符 c 表示天平左右两边分别是 a[] 和 b[],字符 c 表示称量结果, {E: 一样中,L: 左边重,R: 右边重}

输出结果为下一步的其中一种最优称量方案

比如输入:

1
2
3
12 2
4 0 1 2 3 4 5 6 7 E
3 0 1 2 8 9 10 L

程序会输出:

1
8 - 9

表示有12个球,[0 1 2 3] 和 [4 5 6 7] 的称量结果是一样重 [0 1 2] 重于 [8 9 10] 易知坏球在 {8 9 10} 中,下一步比较 8 和 9 即可