牛客练习赛84 D.牛客推荐系统开发之动态特征获取

LINK

作为题的受害者忍不住来写一发题解...

其实就是个简单的模拟,但是数组用混了就非常脑瘫

对n个询问按时间戳排序,并设置一个存机器缓存的特征

是结构体,包含这个缓存的特征类型和优先级,重载<为优先级更小的

优先级使用变量维护,每次加入新的特征类型把即可(后来的优先级一定更大)

那么处理第i个询问的时候,先把所有不符合的时间戳抹去(因为时间戳递增,所以可以用队列维护)

若set中有,就抹去原来的特征类型,把优先级修改为最高,再插入

若set中没有,就一直抹去直到元素个数<m,此时添加

注意

有时候队列中的元素会提前被弹出窗口,此时需要标记一下

遇到被标记的说明已经被抹掉了,队列也向前推进

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
const int N = 1e7+10;
typedef long long ll;
int n,m,y;
struct p
{
    int id,dfn;
    ll t;
    bool operator < (const p&tmp )    const{ return t<tmp.t; }
}a[maxn]; int ans[maxn];
int q[maxn],head = 1,tail,ji[N],jibie,las[10000009];
bool ok[N];
ll tim[10000009];
struct work
{
    int id,you;
    bool operator < ( const work &tmp )    const{    return you<tmp.you;    }
};
set<work>s;
signed main()
{
    cin >> n >> m >> y;
    for(int i=1;i<=n;i++)
    {
        a[i].dfn = i;
        scanf("%d%lld",&a[i].id,&a[i].t );
    }
    sort( a+1,a+1+n );
    for(int i=1;i<=n;i++)
    {
        int id = a[i].id;
        while( head<=tail && ( tim[head]+y<=a[i].t || ok[head] ) )
        {
            if( ok[head]==0 )    s.erase( work{q[head],ji[q[head]]} );
            head++;
        }
        auto v = s.lower_bound( work{id,ji[id]} );
        if( v!=s.end() && ( v->id )==id && ( v->you )==ji[id] )//查询是否在队列中 
        {
            s.erase( work{id,ji[id]} );
            ji[id] = ++jibie;
            s.insert( work{id,ji[id]} );        
            ans[a[i].dfn] = 1;                
        }
        else
        {
            while( s.size()>=m )
            {
                work w = *s.begin();
                ok[ las[w.id] ] = 1;    s.erase( w );
            }
            q[++tail] = id;     tim[tail] = a[i].t; 
            las[id] = tail;        ji[id] = ++jibie;
            s.insert( work{id,ji[id]} );
        }
    }
    for(int i=1;i<=n;i++)    printf(ans[i]==1?"YES\n":"NO\n");
}