共有回帖数 0 个
-
N 个球，有一个是坏的，坏球重量与好球不同（略轻/重于好球）。有一个天平，可以告知左右两边孰重孰轻，最小化最坏情况下称量次数，给出称量方案。
下面讨论该问题的一个扩展——如何通过已知信息（即之前称量结果，之前的称量结果可能不是最优的）选择下一步称量方案，最小化最坏情况下的称量次数。
根据已有信息把所有球分为4类：
0。肯定是好球
1。不可能比好球轻（不能确定是否为坏球）
2。不可能比好球重（不能确定是否为坏球）
3。不知道任何信息
每个球必定属于以上四类中的某一类。我们只需知道每一类的数目即可，具体编号无关紧要。
令 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 实现。
输入格式：
两个整数 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 即可
#include algorithm
#include climits
#include iostream
#include iterator
#include string
#include vector
using namespace std;
typedef vectorint vi;
const int N = 81;
int n, mem[N][N][N];
basic_stringint 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_stringint 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(vectorvi left, vectorvi right, string result)
{
vi p(n, 3);
for (int i = 0; i left.size(); ++i)
if (result == 'E')
{
for (auto it = left.begin(); it != left.end(); ++it)
p[*it] = 0;
for (auto it = right.begin(); it != right.end(); ++it)
p[*it] = 0;
}
else
{
if (result == 'R') left.swap(right);
for (auto it = left.begin(); it != left.end(); ++it)
p[*it] &= ~2;
for (auto it = right.begin(); it != right.end(); ++it)
p[*it] &= ~1;
for (int j = 0; j n; ++j)
if (find(left.begin(), left.end(), j) == left.end()
&& find(right.begin(), right.end(), j) == right.end())
p[j] = 0;
}
for (int i = 0; i n; ++i)
switch (p)
{
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;
vectorvi 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 "errorn";
else if (!res.empty())
{
auto it = find(res.begin(), res.end(), -1);
copy(res.begin(), it, ostream_iteratorint(cout, " "));
cout "- ";
copy(it+1, res.end(), ostream_iteratorint(cout, " "));
cout endl;
}
return 0;
}
楼主 2016-04-21 09:11 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
