• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1013 – Counterfeit Dollar

    ACM-POJ EXP 139阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    有一打(12枚)硬币,其中有且仅有1枚假币,11枚真币

    用A~L作为各个硬币的代号

    假币可能比真币略轻,也可能略重

    现在利用天枰,根据Input输入的3次称量,找出假币,并输出假币是轻还是重。

    解题思路

    模拟法要考虑的情况较繁琐,可利用简单的逻辑推理进行解题。

    注意Input一行代表一次称量,每行有三个字符串,分别为

    Left right status

    代表该次称量时,天枰左盘放的硬币、天枰右盘放的硬币、天枰右盘的状态


    共三种状态

    Up:右盘上升,说明右盘可能有轻假币,也可能左盘有重假币。

    Down:右盘下降,说明右盘可能有重假币,也可能左盘有轻假币。

    Even:右盘与左盘平衡,由于假币有且仅有1枚,则说明此时天枰两边的硬币全为真币。


    注意题目的字眼

    1、 有且仅有1枚假币

    2、 假币相对于真币的重量,可能轻可能重

    3、 只称量3次,且称量3次恰好且必能找到假币

    4、 每次称量时天枰两边的硬币数目一样

    5、 选取哪些硬币称量由input决定

    从3、4、5可知,由于无法知道每次选取称量的硬币,那么3次称量可能只选用了几个硬币,也可能仅有一两个硬币没有选上,那么用模拟法去记录每次用于称量的硬币的状态(真假,其中假币又有轻重之分)并推导没有被称量的硬币状态(或状态变化)是很困难的,虽然人很容易做到这点,但计算机却很难去“推导”,因为称量硬币的方法是无规律的且非常多。

    那么只能通过适当转化问题后用另一种有效的方法去解决。

    虽然称量硬币的方法是无规律且未知的,但是称量硬币后的结果却只有3个,up、down和 even。且当出现even时,天枰两边的硬币必然都为真币,假币必定在余下的硬币之间(这是因为假币有且只有一枚),那么我们就可以定义一个标记数组 zero[]去标记even时的真币,在以后的处理把他们排除在外。

    而唯一难以处理的是up和down的状态,因为假币可能轻可能重,则这两种状态都无法得知究竟假币出现在天枰的哪边。


    处理up和down状态方法

    当出现up或down状态时,天枰两边的所有硬币都应该被怀疑为假币(已标记必定为真币的硬币不必被怀疑)。

    首先time[]记录每个硬币的被怀疑程度,time[i]=0表示该硬币i不被怀疑(即其可能为真币)。定义在up状态盘的硬币为“轻怀疑假币”,通过“--”操作加深其被怀疑为轻假币的程度,“负号”为轻假币的怀疑方向;在down状态盘的硬币为“重怀疑假币”,通过“++”操作加深其被怀疑为重假币的程度,“正号”为重假币的怀疑方向。

    那么若一枚真币被怀疑为“轻假币”时,它就可能通过下次称量通过“++”操作取消嫌疑了。初始化所有硬币的怀疑程度均为0。

    称量完毕后,找出被怀疑程度最大(注意取绝对值)的硬币,它就是假币。而当其怀疑方向为正时,则其为重假币。为负时,为轻假币。


    转载请注明:EXP 技术分享博客 » POJ1013 – Counterfeit Dollar

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址