在13枚硬币中找出fake的那一个

输入:三次天平称量结果

 package poj.ProblemSet;

 import java.util.Scanner;

 /*
我怎么觉得是贪心算法呢?
起初对所有硬币标记0;
如果是even,则两边所有的硬币记为真(记233);
否则就对不确定的硬币记录怀疑(++或者--根据天平倾斜方向);
最后只要看哪个硬币的绝对值最大,也就是被怀疑的次数最多,即是假币。
*/
public class poj1013 {
public static int[] value = new int[20];
public static String[] a = new String[5];
public static String[] b = new String[5];
public static String[] c = new String[5];
public static final int REAL = 233; public static void work(int r, int len, int type) {
if (type == 1) {
for (int i = 0; i < len; i++) {
if (value[a[r].charAt(i)-'A'+1] != REAL) value[a[r].charAt(i)-'A'+1]++;
if (value[b[r].charAt(i)-'A'+1] != REAL) value[b[r].charAt(i)-'A'+1]--;
}
}
else if (type == 2) {
for (int i = 0; i < len; i++) {
if (value[a[r].charAt(i)-'A'+1] != REAL) value[a[r].charAt(i)-'A'+1]--;
if (value[b[r].charAt(i)-'A'+1] != REAL) value[b[r].charAt(i)-'A'+1]++;
}
}
else /*if (type == 3)*/ {
for (int i = 0; i < len; i++) {
value[a[r].charAt(i)-'A'+1] = REAL;
value[b[r].charAt(i)-'A'+1] = REAL;
}
} } public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
for (int n = cin.nextInt(); n-- > 0; ) {
for (int i = 1; i < 20; i++) value[i] = 0;
for (int r = 1; r <= 3; r++) {
a[r] = cin.next();b[r] = cin.next();c[r] = cin.next();int len = a[r].length();
if (c[r].equals("up")) work(r, len, 1);
else if (c[r].equals("down")) work(r, len, 2);
else /*if (c[r].equals("even"))*/ work(r, len, 3);
}
int max = 0,id = 0;
for (int i = 1; i <= 13; i++) {
int val = Math.abs(value[i]);
if (value[i] != REAL && val > max) { max = val;id = i; }
}
System.out.println((char)(id-1+'A') + " is the counterfeit coin and it is " + (value[id]>0?"heavy":"light") + ".");
}
}
}

最新文章

  1. JVM系列-常用参数
  2. OpenStack 通用设计思路 - 每天5分钟玩转 OpenStack(25)
  3. 自动生成数据库字典(sql2008)
  4. LeetCode 374. Guess Number Higher or Lower
  5. hdu 1755 数学 ***
  6. [转]Web.config配置文件详解(新手必看)
  7. 三、python高级特性(切片、迭代、列表生成器、生成器)
  8. 【html】【1】html的简单结构
  9. POJ 2392 Space Elevator DP
  10. SQL Server函数格式
  11. 织梦CMS去广告方法 for DedeCMS V5.7
  12. Altium Designer 18 ------ 常用功能记录
  13. python os详解
  14. az nginx install and other
  15. centos6.6安装hadoop-2.5.0(一、本地模式安装)
  16. 使用 RabbitMQ 实现异步调用
  17. android动手写控件系列——老猪叫你写相机
  18. 洛谷 P4093: bzoj 4553: [HEOI2016/TJOI2016]序列
  19. form action中如何填写相对目录
  20. 【分块】【P2801】教主的魔法

热门文章

  1. Pycharm控制台乱码问题
  2. 权限问题 &lt;customErrors&gt; 标记的“mode”属性设置为“Off”
  3. PAT (Basic Level) Practice (中文)1041 考试座位号 (15 分)
  4. 关于Windows系统下端口被占用的问题和task命令
  5. jQuery中校验时间格式的正则表达式小结
  6. vue必须掌握之组件通信(7种方法)
  7. 在 React 中使用 Typescript
  8. [AT3867] Digit Sum 2
  9. Linux下tomcat端口被占用
  10. matplotlib 的一些知识