Hihocoder 1086 Browser Caching

唉，被这道题坑了一下午。。。

首先题意不难理解，这是一道模拟题，模拟网页的读取原理。

先读入两个整数N和M，分别表示要访问的网页数（N）和能够缓存的网页数（M）。多组测试数组，每组测试数据开始时，默认缓存是空的。当访问每一个网页时，都会有一个“标记”，即该网页时第几个被访问的。当访问一个网页时：

1. 1. 如果缓存是空的（当然是每组数据的第一个网页），那么缓存里会增加一个当前的网页，以及其标记；
   2. 如果缓存非空，先在缓存里寻找是否有当前网页，如果有的话，那么把缓存里该网页的标记（即这个网页是第几个被访问的网页）更新一下；
   3. 如果缓存非空，但是缓存里找不到我们要访问的网页，如果缓存未满（即已经缓存的网页数量<M），那么往缓存里增添当前要访问的网页，以及其标记；
   4. 如果缓存非空，并且缓存里找不到我们要访问的网页，并且缓存已经满了话（即已经缓存的网页数量==M），那么删去缓存里最早被访问的网页（即缓存里标记最小的网页），然后往缓存里增添当前要访问的网页，以及其标记。

我被坑在：当缓存里存在当前要被的访问的网页时，且缓存满时，我都是直接删去标记最小的网页，然后往缓存里增添当前网页及其标记。

而实际上缓存里是不会存在网页名称两两相同的网页的！已哭瞎。。。

上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <fstream>
using namespace std;
struct node
{
    string s;
    int x;
}nn;
vector<node> V;
int N,M;
void test()//调试时用的函数
{
    printf("
");
    if(V.empty())
    {
        printf("Empty

");
        return;
    }
    for(int i=0;i<V.size();i++)
    {
        cout<<V[i].s<<" "<<V[i].x<<"
";
    }
    printf("
");
}
int main()
{
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        V.clear();
        //test();
        cin>>nn.s;
        nn.x=1;
        printf("Internet
");
        V.push_back(nn);
        for(int i=2;i<=N;i++)
        {
            //test();
            cin>>nn.s;
            nn.x=i;
            if(V.size()<M)
            {
                bool f1=false;
                for(int j=0;j<V.size();j++)
                {
                    if(V[j].s==nn.s)
                    {
                        f1=true;
                        V[j].x=nn.x;
                        printf("Cache
");
                        break;
                    }
                }
                if(!f1)
                {
                    V.push_back(nn);
                    printf("Internet
");
                }
            }
            else
            {
                bool f1=false;
                int minn=V[0].x,pos=0;
                if(V[0].s==nn.s)
                {
                    f1=true;
                    V[0].x=nn.x;
                    printf("Cache
");
                    continue;
                }
                for(int j=1;j<M;j++)
                {
                    if(!f1&&V[j].s==nn.s)
                    {
                        f1=true;
                        V[j].x=nn.x;
                        printf("Cache
");
                        break;
                    }
                    if(V[j].x<minn)
                    {
                        minn=V[j].x;
                        pos=j;
                    }
                }
                if(!f1)
                {
                    V[pos].x=nn.x;
                    V[pos].s=nn.s;
                    printf("Internet
");
                }
            }
        }
        //test();
    }
    return 0;
}