題面(from luogu)
（背景： 小晨的電腦上安裝了一個機器翻譯軟件，他經(jīng)常用這個軟件來翻譯英語文章。）
這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義來替換。對于每個英文單詞，軟件會先在內(nèi)存中查找這個單詞的中文含義，如果內(nèi)存中有，軟件就會用它進行翻譯；如果內(nèi)存中沒有，軟件就會在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。
假設內(nèi)存中有 M 個單元，每單元能存放一個單詞和譯義。每當軟件將一個新單詞存入內(nèi)存前，如果當前內(nèi)存中已存入的單詞數(shù)不超過 M?1 ，軟件會將新單詞存入一個未使用的內(nèi)存單元；若內(nèi)存中已存入 M 個單詞，軟件會清空最早進入內(nèi)存的那個單詞，騰出單元來，存放新單詞。
假設一篇英語文章的長度為 N 個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設在翻譯開始前，內(nèi)存中沒有任何單詞。

輸入格式：
共 2 行。每行中兩個數(shù)之間用一個空格隔開。
第一行為兩個正整數(shù) M,N ，代表內(nèi)存容量和文章的長度。
第二行為 N 個非負整數(shù)，按照文章的順序，每個數(shù)（大小不超過 1000 ）代表一個英文單詞。文章中兩個單詞是同一個單詞，當且僅當它們對應的非負整數(shù)相同。
輸出格式：
一個整數(shù)，為軟件需要查詞典的次數(shù)。
樣例.in
3 7
1 2 1 5 4 4 1
樣例.out
5
說明：
每個測試點 1s
對于 10% 的數(shù)據(jù)有 N≤5,M=1 。
對于 100% 的數(shù)據(jù)有 0≤M≤100,0≤N≤1000 。
整個查字典過程如下：每行表示一個單詞的翻譯，冒號前為本次翻譯后的內(nèi)存狀況：
空：內(nèi)存初始狀態(tài)為空。
1． 11 ：查找單詞1并調(diào)入內(nèi)存。
2． 12 ：查找單詞 2 并調(diào)入內(nèi)存。
3． 12 ：在內(nèi)存中找到單詞 1 。
4． 125 ：查找單詞 5 并調(diào)入內(nèi)存。
5． 254 ：查找單詞 4 并調(diào)入內(nèi)存替代單詞 1 。
6． 254 ：在內(nèi)存中找到單詞 4 。
7． 541 ：查找單詞1并調(diào)入內(nèi)存替代單詞 2 。
共計查了 5 次詞典。

題目分析
題目概述：給出一串數(shù)字，共計n個，你有一個長度最多為m的數(shù)字串，如果串中沒有當前遇到的數(shù)字，需要添加，但如*果該串的長度在加上后大于m，則需要向前擠出位子，即是刪去第一個，其他的向前移動一個單位，空出的給新的數(shù)字。（題目的樣例說明說的很清楚）*
大家有沒有發(fā)現(xiàn)，這題很像隊列，先進，先出，所以我們便可以如此結合題目要求，進行模擬了

在對隊列的維護中，我先是寫了一個自己都不知道邏輯（瞎扯）的算法即如下：

t=f[d]; f[d]=p; for(int i = d - 1; i >= 1; i--) {if (i % 2 == 0) //這個就很那什么了。。。額。。。{ t1=f[i]; //兩個變量螺旋交換（無視我在瞎扯）f[i]=t; } else{t=f[i];f[i]=t1; }

這么去維護的話，自然要錯了（AC WA WA WA AC WA AC WA WA WA）,所以想出了這樣的寫法：

for(int i = 1; i <= d-1; i++) f[i]=f[i+1]; //從前向后推 f[d]=p; //霸占擠出的位置

同上面那個額。。。（我也不想多說）好多了。。吧（勉強之笑）

代碼

#include <bits/stdc++.h> using namespace std;int k[10009],f[10009],m,n,i,d=1,ans=1; //d的初值要是1，因為是從第一個開始找的，同樣，ans也要是1，因為第一個數(shù)已經(jīng)調(diào)用了int find(int c) //判讀是否需要維護 {for(int i = 1; i <= d; i++)if (c == f[i]) return 1; //找到了，直接returnreturn 0; //反之，需要進行維護 }void get_more(int p) {int t=0,t1=0;ans++; //進行統(tǒng)計if (d < m) //如果隊列沒有超出其范圍{d++; //向后拓展一個元素位置f[d]=p; //置入}else {// t=f[d]; //惡心的大寶貝// f[d]=p;// for(int i = d - 1; i >= 1; i--)// {// if (i % 2 == 0)// {// t1=f[i];// f[i]=t; // } // else// {// t=f[i];// f[i]=t1; // } for(int i = 1; i <= d-1; i++)f[i]=f[i+1]; //從前向后推f[d]=p; //霸占擠出的位置} }int main() {cin>>m>>n; //輸入for (int i = 1; i <= n; i++)cin>>k[i];f[1]=k[1]; //先取第一個for (int i = 2; i <= n; i++) //開始處理隊列{ if (find(k[i]) == 0) get_more(k[i]); //判斷是否需找// if (d < m) d++; //之前的贅筆，之后再“get_more”函數(shù)中已經(jīng)覆蓋此功能了// for (int i = 1; i <= d; i++)//cout<<f[i]<<' ';// cout<<endl;}// for (int i = 1; i <= m; i++)// cout<<f[i];cout<<ans; //輸出 } **蒟蒻新星c_uizrp_dzjopkl原創(chuàng)**

總結

以上是生活随笔為你收集整理的机器翻译（模拟）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。