AcWing 496. 机器翻译 数组模拟队列解法 && STL+bool数组解法
原题链接
简单
作者:
tocsu
,
2021-02-13 13:33:01
,
所有人可见
,
阅读 353
解法一:$O(n * m)$数组模拟队列。
#include <iostream>
#include <queue>
using namespace std;
int q[1010], hh, tt = -1;
int a[1010];
int main() {
int m, n, c;
cin >> m >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int res = 0;
for (int i = 0; i < n; i++) {
bool flag = false;
for (int j = hh; j <= tt; j++) {
if (q[j] == a[i]) {
flag = true; //说明查找的到
break;
}
}
if (!flag) { //如果没有找到
q[++tt] = a[i];
res++;
}
if (tt - hh + 1 > m) hh++;
}
cout << res << endl;
return 0;
}
解法二 用bool
数组标记 $O(n^2)$解法
#include <iostream>
#include <queue>
using namespace std;
int a[1010];
bool st[1010];
int main() {
int m, n, c;
cin >> m >> n;
for (int i = 0; i < n; i++) cin >> a[i];
queue<int> q;
int res = 0;
for (int i = 0; i < n; i++) {
if (q.size() > m) {
st[q.front()] = false;
q.pop();
}
if (st[a[i]]) continue;
else {
q.push(a[i]);
st[a[i]] = true;
res++;
}
}
cout << res << endl;
return 0;
}