Java程序練習-機器翻譯

機器翻譯
時間限制: 10000ms內存限制: 1024kB
描述
小晨的電腦上安裝了一個機器翻譯軟件，他經常用這個軟件來翻譯英語文章。這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義來替換。對於每個英文單詞，軟件會先在內存中查找這個單詞的中文含義，如果內存中有，軟件就會用它進行翻譯；如果內存中沒有，軟件就會在外存中的詞典內查找，查出單詞的中文含義然後翻譯，並將這個單詞和譯義放入內存，以備後續的查找和翻譯。假設內存中有M個單元，每單元能存放一個單詞和譯義。每當軟件將一個新單詞存入內存前，如果當前內存中已存入的單詞數不超過M−1，軟件會將新單詞存入一個未使用的內存單元；若內存中已存入M 個單詞，軟件會清空最早進入內存的那個單詞，騰出單元來，存放新單詞。
假設一篇英語文章的長度為N 個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設在翻譯開始前，內存中沒有任何單詞。
輸入
輸入文件名為translate.in，輸入文件共2 行。每行中兩個數之間用一個空格隔開。
第一行為兩個正整數M 和N，代表內存容量和文章的長度。
第二行為N 個非負整數，按照文章的順序，每個數（大小不超過1000）代表一個英文
單詞。文章中兩個單詞是同一個單詞，當且僅當它們對應的非負整數相同。
輸出
輸出文件translate.out 共1 行，包含一個整數，為軟件需要查詞典的次數。
樣例輸入
3 7
1 2 1 5 4 4 1
樣例輸出
5
參考代碼

1. /*
2. * machine translation 2011-10-1 12:39PM Eric Zhou
3. */
4. import java.io.BufferedReader;
5. import java.io.IOException;
6. import java.io.InputStreamReader;
7. import java.util.ArrayDeque;
8. import java.util.Set;
9. import java.util.TreeSet;
10. public class Main {
11. public static void main(String[] args) throws IOException {
12. BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
13. String sn[] = cin.readLine().split(" ");
14. int m = Integer.parseInt(sn[0]);
15. int n = Integer.parseInt(sn[1]);
16. String sv[] = cin.readLine().split(" ");
17. int v[] = new int[n];
18. for(int i = 0;i < n;++ i)
19. v[i] = Integer.parseInt(sv[i]);
20. ArrayDeque<Integer>deque = new ArrayDeque<Integer>();
21. Set<Integer>set = new TreeSet<Integer>();
22. int cnt = 0;
23. for(int i = 0;i < n;++ i){
24. if(set.add(v[i])){
25. deque.addLast(v[i]);
26. cnt ++;
27. if(deque.size() > m){
28. set.remove(deque.pollFirst());
29. }
30. }
31. }
32. System.out.println(cnt);
33. }
34. }