| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
给大家提供一个简单的思路,轻拍用三个数组
bool normal[1024];
bool light[1024];
bool heavy[1204];
来保存每一个硬币是 1 肯定没问题, 2 可能是轻的 3 可能是重的
初始化都是false,代表我们什么都不知道
对于每一次测验结果
如果是平局,那么所有参与测验的硬币都肯定没问题
如果是一边轻
那么所有没参与测验的硬币都肯定没问题
而轻的一边则可能是轻的,重的一边可能是重的
这样从信息上没有漏掉任何信息
最后遍历所有硬币
if 他的normal[i]是true,他肯定没问题
else if 他的light[i]和heavy[i]同时是true,他也肯定没问题,因为如果他是轻的或者重的,那么测验结果不可能暗示他既可能轻也可能重
所以这样遍历之后,我们知道每个硬币是安全/不安全的
如果不安全的硬币只有一个,输出之
如果不安全的硬币大于1,输出0
下面贴16MS代码,其实为了可读性麻烦了很多,完全应该0MS
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <math.h>
#include <string>
using namespace std;
#define FOR(x,y) for(int x = 0;x < y;x++)
#define MSET(x) memset(x,0,sizeof(x))
class w// w类保存一次测验结果,提供两个接口验证一个硬币在不在这次测试的左边或者右边
{
public:
w()
{
MSET(l);
MSET(r);
n = 0;
}
int l[512];
int r[512];
bool InLeft(int i)
{
bool ret = false;
FOR(j,n)
{
if (l[j] == i)
{
return true;
}
}
return ret;
}
bool InRight(int i)
{
bool ret = false;
FOR(j,n)
{
if (r[j] == i)
{
return true;
}
}
return ret;
}
int n;
string res;
};
bool normal[1024];
bool light[1024];
bool heavy[1204];
int main()
{
int n,k;
MSET(normal);
MSET(light);
MSET(heavy);
cin>>n>>k;
w * tests = new w[k];
FOR(i,k)
{
cin>>tests[i].n;
FOR(j,tests[i].n)
{
cin>>tests[i].l[j];
}
FOR(j,tests[i].n)
{
cin>>tests[i].r[j];
}
cin>>tests[i].res;
}
FOR(i,k)
{
if (tests[i].res == "=")
{
for(int j = 1; j <= n; j++)
{
if (tests[i].InLeft(j)||tests[i].InRight(j))
{
normal[j] = true;
}
}
}
else if (tests[i].res == "<" || tests[i].res == ">")
{
for (int j = 1; j <= n; j++)
{
if (tests[i].InLeft(j) == false && tests[i].InRight(j) == false)
{
normal[j] = true;
}
else if (tests[i].InLeft(j) && tests[i].res == "<")
{
light[j] = true;
}
else if (tests[i].InLeft(j) && tests[i].res == ">")
{
heavy[j] = true;
}
else if (tests[i].InRight(j) && tests[i].res == "<")
{
heavy[j] = true;
}
else if (tests[i].InRight(j) && tests[i].res == ">")
{
light[j] = true;
}
}
}
}
int ret = 0;
for (int i = 1; i <= n; i++)
{
if (!(normal[i] || (light[i] && heavy[i])))
{
if (ret == 0)
{
ret = i;
}
else
{
ret = 0;
break;
}
}
}
printf("%d\n",ret);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator