题解 P1540 【机器翻译】

Anguei · 2018-02-28 19:53:15 · 题解

此题现有的模拟做法好麻烦啊。我来补充一个 STL 做法。

主要思路是：

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

至此，思路分析完毕，贴上不到 20 行的 AC 代码。

#include <vector>
#include <iostream> 
#include <algorithm>

int main() {
    int m, n, t, ans = 0;
    std::cin >> m >> n;
    std::vector<int> v; // 用来表示内存
    while (std::cin >> t) {
        if (std::find(v.begin(), v.end(), t) == v.end()) { // 如果不在内存中
            v.push_back(t); // 加入内存
            ++ans;
        }
        if (v.size() > m) // 内存满了
            v.erase(v.begin()); // 把第一个单词删掉
    }
    std::cout << ans << std::endl;
}