ACM模版

描述

题解

map+set 搞搞就行了，用 map 打标签，用 set 返回某时某刻的最大值，另外用一个数组 pass 记录网页，相当于队列，如果全部用 STL 应该也是可以过的，不过这里注意要加上输入和输出两个外挂，平时我比较习惯只加输入，可是挂了，超时一组，后来我加上两个外挂后， 875ms 顺顺利利通过！

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>

using namespace std;

const int MAXN = 1000;

int n, k;
int pass[MAXN];
map<int, int> mii;

struct SetCmp
{
    bool operator() (const pair<int, int> &a, const pair<int, int> &b)
    {
        return a.first < b.first || (a.first == b.first && a.second > b.second);
    }
};

set<pair<int, int>, SetCmp> spii;
set<pair<int, int>, SetCmp>::iterator it;

inline void scan_d(int &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

inline void Out(int a)
{
    if (a >= 10)
    {
        Out(a / 10);
    }
    putchar(a % 10 + '0');
}

int main(int argc, const char * argv[])
{
    memset(pass, -1, sizeof(pass));

    scan_d(n);
    scan_d(k);

    int q, id;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        scan_d(q);
        if (q == 1)
        {
            scan_d(id);
            if (!mii[id])
            {
                mii[id]++;
                spii.insert(make_pair(mii[id], id));
            }
            else
            {
                it = spii.find(make_pair(mii[id], id));
                mii[id]++;
                spii.erase(it);
                spii.insert(make_pair(mii[id], id));
            }

            if (pass[cnt] == -1)
            {
                pass[cnt++] = id;
                if (cnt == k)
                {
                    cnt = 0;
                }
            }
            else
            {
                int key = pass[cnt];
                it = spii.find(make_pair(mii[key], key));
                mii[key]--;
                spii.erase(it);
                if (mii[key])
                {
                    spii.insert(make_pair(mii[key], key));
                }
                pass[cnt++] = id;
                if (cnt == k)
                {
                    cnt = 0;
                }
            }
        }
        else
        {
            it = spii.end();
            it--;
            Out(it->second);
            putchar(10);
        }
    }

    return 0;
}