思路

这道题目我用了一个集合和一个队列来维护，集合的作用只是方便查找，当然也可以自己写一个find函数直接在队列里面去找，然后呢队列就是为了模拟题目，跟着题目思路打出来就可以了。

AC代码

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
set<int> s;
int main()
{
    unsigned int n, m, x, sum = 0;
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        if (!s.count(x))
        {
            if (q.size() < m)
            {
                q.push(x);
                s.insert(x);
                sum++;
            }
            else
            {
                s.erase(q.front());
                q.pop();
                q.push(x);
                s.insert(x);
                sum++;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

思路

这道题我用了一个vector和一个变量tail来模拟队列

AC Code:

#include <bits/stdc++.h>
using namespace std;
int m , n , w[1005] , tail , sum;
vector<int> d;
int main()
{
    cin >> m >> n;
    for (int i = 1 ; i <= n ; i++) cin >> w[i];
    for (int i = 1 ; i <= n ; i++)
    {
        bool inD = false;
        for (int j = tail ; j < d.size() ; j++)
        {
            if (w[i] == d[j])
            {
                inD = true;
                break;
            }
        }
        if (!inD)
        {
            d.push_back(w[i]);
            sum++;
        }
        if (d.size() - tail > m) tail++;
    }
    cout << sum;
    return 0;
}

这道题标准模拟，不用看，直接硬模。 题目要求我们输出翻译软件需要去外存查找多少次词典。可以试着用vector做一下

#include <bits/stdc++.h>
using namespace std;
//定义变量
int n,m,x,ans;
//STL用起来（定义vector）
vector<int>v;
//函数查找数字
bool check(vector<int>v1,int x1){
	for (int i=0;i<v1.size();i++){//依次循环，至到找出结果
        if (x1==v[i])return 0;//找到返回false
    }
    return 1;
}
int main(){
    cin>>m>>n;//输入内存与单词数
    //循环求解
    for (int i=1;i<=n;i++){
        cin>>x;//输入
        if (check(v,x)){//如果没有找到该单词在软件里面
            v.push_back(x);//插入该单词
            ans++;
        }
        //如果找到该单词
        if ((int)v.size()>m)v.erase(v.begin());//删除第一个单词
    }
    cout<<ans;//输出
    return 0;
    //全盘模拟
}

算法复杂度为O(n2) 太高！check函数中可以用二分查找来优化。 算法复杂度为O(nlogn)

#include <bits/stdc++.h>
using namespace std;
int n,m,x,ans;
vector<int>v;
bool check(vector<int>v1,int x1){
    int l=0,r=v1.size()-1,mid;
    sort(v1.begin(),v1.end());
    while (l<=r){
        mid=(r+l)/2;
        if (v1[mid]==x1)return 0;
        if (v1[mid]>x1)r=mid-1;
        else l=mid+1;
    }
    return 1;
}
int main(){
    cin>>m>>n;
    for (int i=1;i<=n;i++){
        cin>>x;
        if (check(v,x)){
            v.push_back(x);
            ans++;
        }
        if ((int)v.size()>m)v.erase(v.begin());
    }
    cout<<ans;
    return 0;
}

二分查找也可以用lower_bound()和upper_bound()。

可以发现处理单词的过程类似队列的操作，因此可以使用队列来维护。

#include <bits/stdc++.h>
using namespace std;
int m,n,x,ans;
bool vis[1001];
queue<int> q;
int main(){
    cin>>m>>n;
    while (n--){
        cin>>x;
        if (!vis[x]){//如果不在内存中
            vis[x]=1;//标记此单词进入内存
            if (q.size()==m){
                vis[q.front()]=0;//内存已满，删除最早进入的单词
                q.pop();
            }
            q.push(x);//加入单词队列
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

看着很长实际很简单

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
ll n,m,num,x,a[1001],f,w;
int main(){
    std::ios::sync_with_stdio(0);
    cin>>m>>n;
    for(ll i=1;i<=n;i++){
        cin>>x;
        bool ok=false;
        for(ll i=f;i<w;i++){
            if(a[i]==x){
                ok=true;
                break;
            }
        }
        if(!ok){
            a[w]=x;
            w++;
            num++;
            if(w-f>m){
                f++;
            }
        }
    }
    cout<<num;
    return 0;
}