POJ 1013 称硬币

秒速五厘米 2022-09-29 15:55 146阅读 0赞

先写一组测试数据。

12 ABCD EFGH even ABCI EFJK up ABIJ EFGH even AGHL BDEC even JKI ADE up J K even ABCDEF GHIJKL up ABC DEF even I J down ABCDEF GHIJKL up ABHLEF GDIJKC down CD HA even A B up B A down A C even A B up B C even DEFG HIJL even ABC DEJ down ACH IEF down AHK IDJ down ABCD EFGH even AB IJ even A L down EFA BGH down EFC GHD even BA EF down A B up A C up L K even ACEGIK BDFHJL up ACEGIL BDFHJK down ACEGLK BDFHJI down ACEGIK BDFHJL up ACEGIL BDFHJK down ACEGLK BDFHJI up

这个题目，据说是poj里面称硬币的简单的一个。另外一个上午看了，没做出来。

称硬币，

1.如果天平两边平衡，则这些硬币都是好的。

2.如果不是平衡的，则没在天平上的那些是好的。

3.右侧的coin有up和down之分，根据网上看的别人的经验，设置一个“怀疑度”值，

···如果右侧up，说明右侧的轻了，则把右侧所有的coin怀疑度都加一，左侧怀疑度都减一。

···如果右侧down了，说明右侧的重了，把右侧所有coin怀疑度都减一，左侧怀疑度加一。

4.最终，看怀疑度的绝对值，其中，绝对值最大的那个就是坏的coin。

java代码如下：（代码很臃肿，凑合着看）

import java.util.Scanner; public class Main \{ public static void main(String ss\[\]) \{ Scanner cin = new Scanner(System.in); int count = cin.nextInt(); cin.nextLine(); int\[\] state = new int\[12\]; while (count != 0) \{ count--; int times = 3; for (int i = 0; i < state.length; i++) \{// 初始化状态为0,如果判定为好的coin了，则置为max state\[i\] = 0; \} while (times != 0) \{ times--; String\[\] strs = cin.nextLine().split(" "); char\[\] left = strs\[0\].toCharArray(); char\[\] right = strs\[1\].toCharArray(); String scale = strs\[2\]; if (scale.equals("even")) \{// 如果是even，则两侧的都是好的coin setC(left, state); setC(right, state); \} else if (scale.equals("up")) \{// 右侧的重，右侧加，左侧减。另外，如果是up或者down，则其他的不在这组测试数据中的为好的coin setCO(left, right, state); add(right, state); del(left, state); \} else if (scale.equals("down")) \{// 左侧重，左侧加，右侧减.另外，如果是up或者down，则其他的不在这组测试数据中的为好的coin setCO(left, right, state); add(left, state); del(right, state); \} \} // 三次测试完毕之后，找到出了Max之外的绝对值最大的，然后输出 int coinindex = getAbsMaxIndex(state); if (state\[coinindex\] > 0) \{ char c = (char) (65 + coinindex); System.out.print(c); System.out.print(" is the counterfeit coin and it is "); System.out.println("light."); \} else if (state\[coinindex\] < 0) \{ char c = (char) (65 + coinindex); System.out.print(c); System.out.print(" is the counterfeit coin and it is "); System.out.println("heavy."); \} \} \} // 获得怀疑度最大的那个coin的下标 public static int getAbsMaxIndex(int\[\] state) \{ int index = -1; int max = Integer.MIN\_VALUE; for (int i = 0; i < state.length; i++) \{ if (state\[i\] != Integer.MAX\_VALUE && max < Math.abs(state\[i\])) \{ max = Math.abs(state\[i\]); index = i; \} \} return index; \} // 设置为好的coin public static void setC(char\[\] cs, int\[\] state) \{ for (int i = 0; i < cs.length; i++) \{ switch (cs\[i\]) \{ case 'A': state\[0\] = Integer.MAX\_VALUE; break; case 'B': state\[1\] = Integer.MAX\_VALUE; break; case 'C': state\[2\] = Integer.MAX\_VALUE; break; case 'D': state\[3\] = Integer.MAX\_VALUE; break; case 'E': state\[4\] = Integer.MAX\_VALUE; break; case 'F': state\[5\] = Integer.MAX\_VALUE; break; case 'G': state\[6\] = Integer.MAX\_VALUE; break; case 'H': state\[7\] = Integer.MAX\_VALUE; break; case 'I': state\[8\] = Integer.MAX\_VALUE; break; case 'J': state\[9\] = Integer.MAX\_VALUE; break; case 'K': state\[10\] = Integer.MAX\_VALUE; break; case 'L': state\[11\] = Integer.MAX\_VALUE; break; \} \} \} // 把除了cs中的其他的设置为好的coin public static void setCO(char\[\] cs1, char\[\] cs2, int\[\] state) \{ char\[\] cs = new char\[cs1.length + cs2.length\]; for (int i = 0; i < cs1.length; i++) \{ cs\[i\] = cs1\[i\]; \} for (int i = 0; i < cs2.length; i++) \{ cs\[i + cs1.length\] = cs2\[i\]; \} // 先找到不在cs中的那些字符 char\[\] c4 = findNotInCS(cs); for (int i = 0; i < c4.length; i++) \{ switch (c4\[i\]) \{ case 'A': state\[0\] = Integer.MAX\_VALUE; break; case 'B': state\[1\] = Integer.MAX\_VALUE; break; case 'C': state\[2\] = Integer.MAX\_VALUE; break; case 'D': state\[3\] = Integer.MAX\_VALUE; break; case 'E': state\[4\] = Integer.MAX\_VALUE; break; case 'F': state\[5\] = Integer.MAX\_VALUE; break; case 'G': state\[6\] = Integer.MAX\_VALUE; break; case 'H': state\[7\] = Integer.MAX\_VALUE; break; case 'I': state\[8\] = Integer.MAX\_VALUE; break; case 'J': state\[9\] = Integer.MAX\_VALUE; break; case 'K': state\[10\] = Integer.MAX\_VALUE; break; case 'L': state\[11\] = Integer.MAX\_VALUE; break; \} \} \} // 查找A-L中，不在even中的那些字符 public static char\[\] findNotInCS(char\[\] cs) \{ String c4 = ""; for (int i = 0; i < 12; i++) \{// 一共从A到L 12个字符 char c = (char) (65 + i); if (!charInCS(c, cs)) \{ c4 += c; \} \} return c4.toCharArray(); \} public static boolean charInCS(char c, char\[\] cs) \{ for (int i = 0; i < cs.length; i++) \{ if (c == cs\[i\]) return true; \} return false; \} // 减1 public static void del(char\[\] cs, int\[\] state) \{ for (int i = 0; i < cs.length; i++) \{ switch (cs\[i\]) \{ case 'A': if (state\[0\] != Integer.MAX\_VALUE) \{ state\[0\] = state\[0\] - 1; \} break; case 'B': if (state\[1\] != Integer.MAX\_VALUE) \{ state\[1\] = state\[1\] - 1; \} break; case 'C': if (state\[2\] != Integer.MAX\_VALUE) \{ state\[2\] = state\[2\] - 1; \} break; case 'D': if (state\[3\] != Integer.MAX\_VALUE) \{ state\[3\] = state\[3\] - 1; \} break; case 'E': if (state\[4\] != Integer.MAX\_VALUE) \{ state\[4\] = state\[4\] - 1; \} break; case 'F': if (state\[5\] != Integer.MAX\_VALUE) \{ state\[5\] = state\[5\] - 1; \} break; case 'G': if (state\[6\] != 6) \{ state\[6\] = state\[6\] - 1; \} break; case 'H': if (state\[7\] != Integer.MAX\_VALUE) \{ state\[7\] = state\[7\] - 1; \} break; case 'I': if (state\[8\] != Integer.MAX\_VALUE) \{ state\[8\] = state\[8\] - 1; \} break; case 'J': if (state\[9\] != Integer.MAX\_VALUE) \{ state\[9\] = state\[9\] - 1; \} break; case 'K': if (state\[10\] != Integer.MAX\_VALUE) \{ state\[10\] = state\[10\] - 1; \} break; case 'L': if (state\[11\] != Integer.MAX\_VALUE) \{ state\[11\] = state\[11\] - 1; \} break; \} \} \} // 加1 public static void add(char\[\] cs, int\[\] state) \{ for (int i = 0; i < cs.length; i++) \{ switch (cs\[i\]) \{ case 'A': if (state\[0\] != Integer.MAX\_VALUE) \{ state\[0\] = state\[0\] + 1; \} break; case 'B': if (state\[1\] != Integer.MAX\_VALUE) \{ state\[1\] = state\[1\] + 1; \} break; case 'C': if (state\[2\] != Integer.MAX\_VALUE) \{ state\[2\] = state\[2\] + 1; \} break; case 'D': if (state\[3\] != Integer.MAX\_VALUE) \{ state\[3\] = state\[3\] + 1; \} break; case 'E': if (state\[4\] != Integer.MAX\_VALUE) \{ state\[4\] = state\[4\] + 1; \} break; case 'F': if (state\[5\] != Integer.MAX\_VALUE) \{ state\[5\] = state\[5\] + 1; \} break; case 'G': if (state\[6\] != Integer.MAX\_VALUE) \{ state\[6\] = state\[6\] + 1; \} break; case 'H': if (state\[7\] != Integer.MAX\_VALUE) \{ state\[7\] = state\[7\] + 1; \} break; case 'I': if (state\[8\] != Integer.MAX\_VALUE) \{ state\[8\] = state\[8\] + 1; \} break; case 'J': if (state\[9\] != Integer.MAX\_VALUE) \{ state\[9\] = state\[9\] + 1; \} break; case 'K': if (state\[10\] != Integer.MAX\_VALUE) \{ state\[10\] = state\[10\] + 1; \} break; case 'L': if (state\[11\] != Integer.MAX\_VALUE) \{ state\[11\] = state\[11\] + 1; \} break; \} \} \} \}