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. }