2503:Babelfish

总时间限制: 3000ms 内存限制: 65536kB

描述
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.

输入
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.

输出
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as “eh”.
英文看的头疼，还是转成中文吧

2503：通天鱼

描述
您刚刚从滑铁卢搬到了一个大城市。这里的人说的是一门不可理解的外语。幸运的是，您有一本字典可以帮助您理解它们。

输入
输入最多包含100,000个字典条目，后跟一个空白行，然后是最多100,000个单词的消息。每个字典条目都是一行，其中包含一个英文单词，后跟一个空格和一个外语单词。在词典中，没有外来词出现多次。该消息是外语单词序列，每行一个单词。输入中的每个单词最多包含10个小写字母的序列。

输出
输出是将消息翻译成英语，每行一个单词。词典中未出现的外来词应翻译为“ eh”。

样例输入

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

样例输出

cat
eh
loops

解题思路
由于词条量非常的大，所以使用二分查找。对于查找字符串，要用到字符串排序。较简单得做法是建立字符串对得结构体，然后定义entry类实现comparable接口，重写cmp（）方法完成排序。

参考程序

import java.util.*;

class Entry implements Comparable<Entry>{
	String eng;
	String frgn;
	@Override
	public int compareTo(Entry arg0){
		return this.frgn.compareTo(arg0.frgn);
	}
}
class cmp  implements Comparator<Entry>{
	@Override
	public int compare(Entry o1,Entry o2){
		return o1.frgn.compareTo(o2.frgn);
		
	}
}
public class Main {

public static void main(String[] args) {
	Scanner sc =new Scanner(System.in);
	int num=0;
	ArrayList<Entry> list = new ArrayList<>();
	while(true){
		String s = sc.nextLine();
		if(s.equals("")){break;}
		String[] split = s.split(" ");
		Entry entry = new Entry();
		entry.eng = split[0];
		entry.frgn = split[1];
		list.add(entry);
	}
	Collections.sort(list,new cmp());
	while(sc.hasNext()){
		String word = sc.nextLine();
		int left=0,right = list.size()-1;
		int n=0;
		while(left<=right){
			int mid = (left+right)/2;
			String tmp =list.get(left).frgn;
			String frgn1 =list.get(mid).frgn;
			n = frgn1.compareTo(word);
			if(n<0){
				left = mid +1;
			}else if(n>0){
				right = mid-1;
			}else{
				System.out.println(list.get(mid).eng);
				break;
			}
		}
		if(n!=0){System.out.println("eh");}
	}
}
}

附上原题链接http://bailian.openjudge.cn/practice/2503