称球问题扩展——根据当前已知信息选择最优称量方案
似乎是某个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类) 一边。
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 实现。
#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: 右边重}
输出结果为下一步的其中一种最优称量方案
比如输入：
12 2
4 0 1 2 3 4 5 6 7 E
3 0 1 2 8 9 10 L程序会输出：
8 - 9表示有12个球，[0 1 2 3] 和 [4 5 6 7] 的称量结果是一样重 [0 1 2] 重于 [8 9 10] 易知坏球在 {8 9 10} 中，下一步比较 8 和 9 即可