M_sea

洛谷4404 [JSOI2010]缓存交换
LuoguBZOJ分析贪心。如果 $\mathrm{cache}$ 没有满,那么直接丢进去即可。如果满了的话,考虑...
扫描右侧二维码阅读全文
18
2019/04

洛谷4404 [JSOI2010]缓存交换

Luogu

BZOJ

分析

贪心。

如果 $\mathrm{cache}$ 没有满,那么直接丢进去即可。

如果满了的话,考虑丢掉哪个。显然丢到下一次出现最靠后的那个是最优的。

用一个堆来维护目前所有 $\mathrm{cache}$ 中的数据上一个出现位置。因为需要删除,所以可以在 $\mathrm{priority\_queue}$ 的基础上打删除标记。

这么讲似乎并不清楚,可以结合代码理解一下。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;
int a[N],s[N];
int lst[N],nxt[N],vis[N];

struct node { int p; };
bool operator <(node a,node b) { return nxt[a.p]<nxt[b.p]; }

struct heap {
    priority_queue<node> Q;
    int delv[N];

    inline void push(int u) { Q.push((node){u}); }
    inline void del(int u) { delv[u]=1; }
    inline int top() {
        while (delv[Q.top().p]) delv[Q.top().p]=0,Q.pop();
        return Q.top().p;
    }
    inline void pop() {
        while (delv[Q.top().p]) delv[Q.top().p]=0,Q.pop();
        Q.pop();
    }
} Q;

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) s[i]=a[i]=read();
    sort(s+1,s+n+1); int o=unique(s+1,s+n+1)-s-1;
    for (re int i=1;i<=n;++i) a[i]=lower_bound(s+1,s+o+1,a[i])-s;
    memset(lst,0x3f,sizeof(lst));
    for (re int i=n;i;--i) nxt[i]=lst[a[i]],lst[a[i]]=i;
    int ans=0;
    for (re int i=1,tot=0;i<=n;++i) {
        if (vis[a[i]]) {
            Q.del(vis[a[i]]),vis[a[i]]=i,Q.push(vis[a[i]]);
            continue;
        }
        if (tot<m) Q.push(i),vis[a[i]]=i,++tot,++ans;
        else {
            int j=Q.top(); Q.pop(); vis[a[j]]=0;
            Q.push(i); vis[a[i]]=i;
            ++ans;
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 04 月 18 日 11 : 50 AM

发表评论