算法 POJ1029

一．题目大意

假币

描述

“金条”银行从可靠来源收到的信息，在他们最后一组的 N 枚硬币中，恰好有一枚硬币是假的，并且重量与其他硬币不同（而所有其他硬币的重量都相同）。经济危机之后，他们只有一个简单的余额可用（如图所示）。使用此天平，可以确定左侧盘中物体的重量是否小于、大于或等于右侧盘中物体的重量。
为了检测假币，银行员工用从 1 到 N 的整数对所有硬币进行编号，从而为每个硬币分配一个唯一的整数标识符。之后，他们开始在左盘和右盘中放置相同数量的硬币，对各种硬币组进行称重。硬币的标识符和加权结果被仔细记录下来。
您将编写一个程序，帮助银行员工使用这些加权结果确定假币的标识符。

输入

输入文件的第一行包含两个整数 N 和 K，用空格分隔，其中 N 是硬币的数量 （2<=N<=1000 ），K 是完成的加权数量 （1<=K<=100）。以下 2K 行描述了所有权重。两条连续的线描述每个权重。第一个以数字 Pi （1<=Pi<=N/2） 开头，代表放置在左侧和右侧盘中的硬币数量，然后是放置在左侧盘中的硬币的 Pi 标识符和放置在右侧盘中的硬币的 Pi 标识符。所有数字都用空格分隔。第二行包含以下字符之一：'<'、'>' 或 '=“。它表示加权的结果：
'<' 表示左盘中硬币的重量小于右盘中硬币的重量，
'>' 表示左盘中硬币的重量大于右盘中硬币的重量，
'=' 表示左盘中硬币的重量等于右盘中硬币的重量。

输出

将假币的标识符写入输出文件，如果给定加权的结果无法找到，则为 0。

样本输入

5 3

2 1 2 3 4

<

1 1 4

=

1 2 5

=

示例输出

3

二．题意理解与分析

这是一道通过对天平称重结果进行分析来找出假币的问题，并非运用特定经典算法（如dijkstra算法等）的变形题。问题中已知有N枚硬币（2 <= N <= 1000），其中仅有1枚为假币且与其他真币重量不同，通过对不同硬币组合进行K次（1 <= K <= 100）称重，每次称重记录左右盘放置的硬币数量及具体硬币标识符，以及称重结果（左盘重量小于、大于或等于右盘重量）。我们需要根据这些称重信息，设计程序来确定假币的标识符，若无法明确则输出0。解题的关键在于合理利用数组记录每次称重对各硬币“重量特征”的影响以及标记真币，进而通过对这些数据的分析判断出假币。

三．算法思路分析

首先初始化记录硬币 “权重变化” 的weight数组和标记真币的flag数组为 0 。接着读取硬币数量n和称重次数k，对每次称重，记录左右盘硬币数量和编号，并依据称重结果进行处理：若结果为 “=”，则将对应硬币标记为真币；若为 “>” 或 “<”，则相应增减左右盘硬币在weight数组中的值，并记录称重次数。最后遍历所有未标记为真币的硬币，若其weight值等于或为负的称重次数，则认为可能是假币，统计可能假币数量，若数量大于 1 则无法确定假币输出 0 ，否则输出该可能假币的编号。

四．源代码

五．总结

通过编写解决“金条”银行假币检测问题的程序，巩固了对数据结构和逻辑推理的运用，在代码中利用数组记录硬币称重相关信息并进行分析处理以找出假币。虽未涉及贪心选择算法和分治法，但此次实践锻炼了解决问题的能力，让我明白不能思维固化，要根据不同问题灵活运用方法，牢记算法性质、场景和步骤，从而扩展解题思维广度，例如本题根据称重结果巧妙标记和统计来确定假币，为今后解决类似问题积累了经验。