题意：十二枚硬币中有一个与其它重量不一样，用天平只称三次，请推断出哪一枚银币与其它不一样，是轻了还是重了？
这是一道to satisty题目，就是去满足给定的条件。
解这类题目的思路有两种：
方法一、假设不知道那一枚硬币有问题，根据条件推测出有问题的硬币。
方法二、依次假设硬币有问题，看那种假设满足题意。
显然，这类题目用第二种方法更好做，因为可以假设的情况是很少的。只需要把所有出现的硬币都“怀疑”一遍就可以得到正确结果了。

代码
1

import java.io.*;
2

import java.util.*;
3

class Main
4

{
5

public static void main(String[] args)
7

{
8

Scanner sc = new Scanner(System.in);
9

int n = sc.nextInt();
10

sc.nextLine();
11

for(int i = 0; i < n; i++)
12

{
13

String strs[] = new String[3];
14

strs[0] = sc.nextLine();
15

strs[1] = sc.nextLine();
16

strs[2] = sc.nextLine();
17

getRS(strs);
19

}
20

}
21

private static void getRS(String[] strs){
22

TreeSet<Character> trset = new TreeSet<Character>();
23

int[] weights = new int[300];
24

for(int i = 0; i < 3; i++)
25

{
26

char[] chArry = strs[i].toCharArray();
27

for(int j = 0; j < chArry.length; j++)
28

{
29

if(Character.isUpperCase(chArry[j]))
30

{
31

trset.add(chArry[j]);
32

}
33

}
34

}
35

for(char ch : trset)// may light
36

{
37

//System.out.println("ch=" + ch);
38

Arrays.fill(weights, 0);
39

weights[ch] = -1;
40

boolean success = true;
41

for(int i = 0; i < 3; i++)
42

{
43

String[] strArry = strs[i].split(" ");
44

int wl = 0;
45

int wr = 0;
46

char[] chArry2 = strArry[0].toCharArray();
47

for(char ch2 : chArry2)
48

{
49

wl += weights[ch2];
50

}
51

char[] chArry3 = strArry[1].toCharArray();
52

for(char ch3 : chArry3)
53

{
54

wr += weights[ch3];
55

}
56

if(!getRSString(wl, wr).equals(strArry[2]))
57

success = false;
58

}
59

if(success)
60

{
61

System.out.println(ch + " is the counterfeit coin and it is light.");
62

return;
63

}
64

}
65

//
66

for(char ch : trset)// may heavy
67

{
68

Arrays.fill(weights, 0);
70

weights[ch] = 1;
71

boolean success = true;
72

for(int i = 0; i < 3; i++)
73

{
74

String[] strArry = strs[i].split(" ");
75

int wl = 0;
76

int wr = 0;
77

char[] chArry2 = strArry[0].toCharArray();
78

for(char ch2 : chArry2)
79

{
80

wl += weights[ch2];
81

}
82

char[] chArry3 = strArry[1].toCharArray();
83

for(char ch3 : chArry3)
84

{
85

wr += weights[ch3];
86

}
87

if(!getRSString(wl, wr).equals(strArry[2]))
88

success = false;
89

}
90

if(success)
91

{
92

System.out.println(ch + " is the counterfeit coin and it is heavy.");
93

return;
94

}
95

}
96

}
97

private static String getRSString(int wl, int wr)
98

{
99

if(wl == wr)
100

return "even";
101

if(wl > wr)
102

return "up";
103

return "down";
104

}
105

106

}
107

posted on 2013-03-22 22:31 小鼠标阅读(152) 评论(0) 编辑收藏引用所属分类: Java基础练习

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 编辑距离闰年判断正则表达式简单笔记 Excel格式地址转换一道模拟题——机器人行走距离计算排列练习2 素数筛法排列组合练习排列组合 poj1068Parencodings

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2012年7月

日

一

二

三

四

五

六

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

阅读排行榜