hihoCoder#1086 Browser Caching

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

原题地址

list+map可以轻松搞定，如果不借助STL实现起来还是挺麻烦的

代码：

 #include <iostream>

 #include <string>

 #include <list>

 #include <map>

 using namespace std;

 int N, M;

 map<string, list<string>::iterator> record;

 list<string> cache;

 int size = ;

 int main() {

   string url;

   cin >> N >> M;

   while (N--) {

     cin >> url;

     auto p = record.find(url);

     if (p != record.end()) {

       cache.erase(p->second);

       cache.push_front(p->first);

       cout << "Cache" << endl;

     }

     else if (size >= M){

       record.erase(cache.back());

       cache.pop_back();

       cache.push_front(url);

       record.insert(pair<string, list<string>::iterator>(url, cache.begin()));

       cout << "Internet" << endl;

     }

     else {

       cache.push_front(url);

       size++;

       record.insert(pair<string, list<string>::iterator>(url, cache.begin()));

       cout << "Internet" << endl;

     }

   }

   return ;

 }