[NOIP2010 提高組] 機器翻譯

題目背景

NOIP2010 提高組 T1

題目描述

小晨的電腦上安裝了一個機器翻譯軟件，他經(jīng)常用這個軟件來翻譯英語文章。

這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應(yīng)的中文含義來替換。對于每個英文單詞，軟件會先在內(nèi)存中查找這個單詞的中文含義，如果內(nèi)存中有，軟件就會用它進(jìn)行翻譯；如果內(nèi)存中沒有，軟件就會在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。

假設(shè)內(nèi)存中有 $M$ 個單元，每單元能存放一個單詞和譯義。每當(dāng)軟件將一個新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過 $M?1$，軟件會將新單詞存入一個未使用的內(nèi)存單元；若內(nèi)存中已存入 $M$ 個單詞，軟件會清空最早進(jìn)入內(nèi)存的那個單詞，騰出單元來，存放新單詞。

假設(shè)一篇英語文章的長度為 $N$ 個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開始前，內(nèi)存中沒有任何單詞。

輸入格式

共 $2$ 行。每行中兩個數(shù)之間用一個空格隔開。

第一行為兩個正整數(shù) $M,N$，代表內(nèi)存容量和文章的長度。

第二行為 $N$ 個非負(fù)整數(shù)，按照文章的順序，每個數(shù)（大小不超過 $1000$）代表一個英文單詞。文章中兩個單詞是同一個單詞，當(dāng)且僅當(dāng)它們對應(yīng)的非負(fù)整數(shù)相同。

輸出格式

一個整數(shù)，為軟件需要查詞典的次數(shù)。

樣例 #1

樣例輸入 #1

3 7
1 2 1 5 4 4 1

樣例輸出 #1

5

提示

樣例解釋

整個查字典過程如下：每行表示一個單詞的翻譯，冒號前為本次翻譯后的內(nèi)存狀況：

1. 1：查找單詞 1 并調(diào)入內(nèi)存。
2. 1 2：查找單詞 2 并調(diào)入內(nèi)存。
3. 1 2：在內(nèi)存中找到單詞 1。
4. 1 2 5：查找單詞 5 并調(diào)入內(nèi)存。
5. 2 5 4：查找單詞 4 并調(diào)入內(nèi)存替代單詞 1。
6. 2 5 4：在內(nèi)存中找到單詞 4。
7. 5 4 1：查找單詞 1 并調(diào)入內(nèi)存替代單詞 2。

共計查了 $5$ 次詞典。

數(shù)據(jù)范圍

• 對于 $10\%$ 的數(shù)據(jù)有 $M=1$，$N\le 5$；
• 對于 $100\%$ 的數(shù)據(jù)有 $1\le M\le 100$，$1\le N\le 1000$。

提交代碼

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int quee[N]={-1}, a[N], n, m;
int l, k,sum;
bool flag = false;
int main()
{cin >> n >> m;for (int i = 0; i < m; i++){cin >> a[i];if (a[i] == 0)a[i] = -1;}for (int i = 0; i < m; i++){flag = false;for (int j = l; j < n; j++){if (a[i] == quee[j]){flag = true;break;}}if (!flag){quee[k++] = a[i];sum++;}if (k > n){quee[l++] = -1;n++;}}cout << sum << endl;return 0;
}

代碼思路總結(jié)

• 輸入處理：
  • 讀取內(nèi)存容量 n 和文章長度 m。
  • 讀取文章中的單詞序列 a[]，并將值為 0 的單詞替換為 -1（為了避免與未初始化的隊列元素沖突）。
• 邏輯處理：
  • 遍歷文章中的每個單詞：
    • 檢查當(dāng)前單詞是否已經(jīng)在內(nèi)存隊列 quee[] 中。
    • 如果單詞不在內(nèi)存中，則將其加入隊列，并增加查詞典次數(shù) sum。
    • 如果隊列已滿（k > n），則移除最早進(jìn)入隊列的單詞（通過移動左指針 l）。
• 輸出結(jié)果：
  • 輸出查詞典的總次數(shù) sum。

算法刷題記錄