題目背景

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

題目描述

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

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

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

輸入格式

共22行。每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。

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

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

輸出格式

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

思路

這道題其實(shí)異常的簡(jiǎn)單，模擬唄，它說(shuō)啥就是啥唄
首先我們開(kāi)兩個(gè)數(shù)組
vis數(shù)組和time數(shù)組

vis數(shù)組：判斷i是否在本地內(nèi)存中，是則為1，否則為0

time數(shù)組：記錄time[i]進(jìn)入內(nèi)存的時(shí)間

然后定義倆變量，分別為l,r，l記錄目前最早進(jìn)入內(nèi)存的變量，r記錄當(dāng)前最新進(jìn)入內(nèi)存的變量

只要當(dāng)沒(méi)有內(nèi)存時(shí)（r = m），那么time[l]更新，l=l+1，vis[t]更新
如果有內(nèi)存就正常存進(jìn)去，由于時(shí)間緊迫，先貼代碼（后面會(huì)補(bǔ)上的）

#include <cstdio>
using namespace std;

int vis[1005];
int time[1005];
int l, r;
int ans;

int main(int argc, char const *argv[])
{
    int n, m, t;
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &t);

        if(vis[t] == 0)//如果內(nèi)存中并無(wú)這個(gè)數(shù)（單詞）
        {
            ans++;//答案+1
            r++;//最后一個(gè)存入的數(shù)更新
            time[r] = t;//賦值
            vis[t] = 1;//更新內(nèi)存

            if(r > m) //如果內(nèi)存為0
                l++,vis[time[l]] = 0;//最先存入的數(shù)更新，清空內(nèi)存
        }
    }   
    printf("%d", ans);
    return 0;
}