当前位置: 代码迷 >> 综合 >> POJ1013 Counterfeit Dollar(技巧)
  详细解决方案

POJ1013 Counterfeit Dollar(技巧)

热度:18   发布时间:2024-01-16 13:58:02.0

题意:

有十二枚硬币,其中有一枚假币与其他真币重量不同,但不知道是轻是重,通过称量三次确定这枚硬币的字母代号

要点:

题目中没有说每次称量几枚硬币,所以用模拟非常复杂,这里有一个比较特别的技巧:

先如果天平是平衡的,那么对于的所以硬币肯定是真的,用一个数组存储将这些硬币剔除,后面计算时就不用考虑了。因为不知道假币是轻还是重,那么如果出现up和down,那么肯定这其中有假币,但是不知道是那边的。那么我们应该先把两边的硬币都看成假币(不包括已经确定是真的硬币),另设一个数组time,如果是up,那么右盘的硬币怀疑为“轻假币”,对应的time--:而左盘怀疑为“重假币”,对应的time++。如果是down同样这么处理。再取time数组中绝对值最大的那个就是假币,对应的time>0说明是重币,反之是轻币。

我是这么理解的:假币每次出现都会造成对应的time或增或减,但绝对是只增加或只减少的。而真币如果被怀疑成轻假币,下一次称量时也可能被++从而降低了怀疑程度。总而言之只有一枚假币,而且是肯定可以求出来的,所以绝对值最大的肯定只有一个对应的即为假币。

参考的博客:点击打开链接