终于AC了,原来我一直以为输入是四个字符,四个字符输入的,晕!不过后来还是就解决了哈哈!好了,开始说正题吧!
题意:有12个硬币,其中有一个和其他的硬币重量不一样,然后小X用3次天平称称量这些硬币。输入3组数据样式是“字符字符 字符字符 even|up|down”字符个数不定!!在网上看到过计算在天平不平衡的时候字符出现的次数多少来判断的算法,这里我用了其他的算法,虽然有点麻烦但是效果还是好的。我的做法是,先弄两个数组其中一个是A--L的标识符,如果是1则说明它被确认位真硬币,其他数字则有可能是假币,还有一个数组时字符串数组,来表示如果一个字母在不平衡称量那次里面出现时,并且不能确认他是真的硬币的时候,那么设定一个假设它就是假硬币的时候的light|heavy(有可能是真币,但是这不影响结果,因为真币是不输出的 :) )。我们来演示一次输入吧。就题目上的例子好了
输入: 1 //在这里caseNum的输入不讲。
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
1.对A--L 12个字母都标记为0进行初始化。
2.输入第一行ABCD EFGH even 先进行第三个字符串的even|up|down的辨别因为是even所以在这里出现的字符全标记为1。则:
A B C D E F G H I J K L
1 1 1 1 1 1 1 1 0 0 0 0
3.输入第二行ABCI EFJK up 不是even所以这里有的字母除去原本标识符是1的标识符变为2即。并且最后没出现的字符也标识为1。并且记录相应的light|heavy
A B C D E F G H I J K L
1 1 1 1 1 1 1 1 2 2 2 1
4.输入第三行ABIJ EFGH even 在这里出现的字符全部标识为1.
A B C D E F G H I J K L
1 1 1 1 1 1 1 1 1 1 2 1
最后得出K的值不一样,输出结果。注意:如果一个字符在两次不平衡中的light|heavy不一样,那么也需要将其标识为1.因为一个硬币不可能即为轻又为重。以下是全部代码:
分享到:
相关推荐
北大1000题至2000部分题的源代码...
pku acm 第3356题 AGTC Java代码,有详细的注释,动态规划
pku acm 第1953题World Cup Noise c完整的代码,有详细的注释
Pku acm 第1159题 Palindrome 代码,有详细的注释,动态规划
pku acm 动态规划题1179解题报告
Pku acm 第2192题 Zipper 代码,有详细的注释,动态规划
Pku acm 第1458题 Common Subsequence 代码,有详细的注释,动态规划
Pku acm 第1125题 Stockbroker Grapevine c代码,有详细的注释,动态规划,使用弗洛伊德算法
Pku acm 第3253题 Fence Repair 代码,有详细的注释,哈夫曼数
Pku acm 第1160题 Post Office 代码,有详细的注释,动态规划
Pku acm 第1631题 Bridging signals 代码,有详细的注释,动态规划
pku2482--Stars in Your Window的源程序
Pku acm 第1579题 Function Run Fun 代码,有详细的注释,动态规划
Pku acm 第1157题 LITTLE SHOP OF FLOWERS c代码,有详细的注释,动态规划
Pku acm 第1163题 The Triangle 代码,有详细的注释,动态规划
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
Pku acm 第1887题 Testing the CATCHER 代码,有详细的注释,动态规划
pku acm 1258 Agri-Net代码 最小生成树的prim算法,有详细的注释
pku acm 2299 Ultra-QuickSort代码,合并排序求逆序数,解题报告请访问:http://blog.csdn.net/china8848
在POJ上做的一些动态规划题,自己看吧。