「NOIp2010」机器翻译-模拟+Vector

因为作者太菜了所以还是无法简洁高效的描述题目

Luogu P1540

Solution

显然的,我们可以

  • 使用一个 vector 来表示内存。
  • 依次读如数据,判断是否在内存中(find)。如果不在,就需要查词典,然后加入内存、将答案 + 1。
  • 如果内存满了,就把最先进入内存的单词删掉(erase)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>      
#define pb push_back
using namespace std;

inline int read(){
int sum=0,fl=1,ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') fl=-1;
for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
return sum*fl;
}

vector <int> a;

int main(){
int m,n,x,ans=0;
m=read();
n=read();
for(int i=1;i<=n;i++){
x=read();
if(find(a.begin(),a.end(),x)==a.end()){ //a.end()指向迭代器中末端元素的下一个,即一个不存在元素。
a.pb(x);
++ans;
}
if(a.size()>m) a.erase(a.begin()); //将起始位置的元素删除
}
printf("%d\n",ans);
return 0;
}