BZOJ_1826_[JSOI2010]缓存交换 _线段树+贪心
Description
在计算机中，CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时，则需要从主存里把数据调入Cache。此时，如果Cache容量已满，则必须先从中删除一个。 例如，当前Cache容量为3，且已经有编号为10和20的主存单元。 此时，CPU访问编号为10的主存单元，Cache命中。 接着，CPU访问编号为21的主存单元，那么只需将该主存单元移入Cache中，造成一次缺失（Cache Miss）。 接着，CPU访问编号为31的主存单元，则必须从Cache中换出一块，才能将编号为31的主存单元移入Cache，假设我们移出了编号为10的主存单元。 接着，CPU再次访问编号为10的主存单元，则又引起了一次缺失。我们看到，如果在上一次删除时，删除其他的单元，则可以避免本次访问的缺失。 在现代计算机中，往往采用LRU(最近最少使用)的算法来进行Cache调度——可是，从上一个例子就能看出，这并不是最优的算法。 对于一个固定容量的空Cache和连续的若干主存访问请求，聪聪想知道如何在每次Cache缺失时换出正确的主存单元，以达到最少的Cache缺失次数。
Input
输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。 第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。
Output
输出一行，为Cache缺失次数的最小值。
Sample Input
6 2
1 2 3 1 2 3
1 2 3 1 2 3
Sample Output
4
HINT
在第4次缺失时将3号单元换出Cache。
考虑x数某次出现的位置到它下一次出现的位置这段区间。
如果我想要让x不缺失，需要在这段区间里让x进入cache，相当于在这个区间塞一个数。
那么整个序列中，每个位置中最多能塞入m-1个数，因为x这个数已经在cache里了。
然后就变成了另一道题：http://www.cnblogs.com/suika/p/8711400.html
代码：
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define N 200050#define ls p<<1#define rs p<<1|1int n,m;int t[N<<2],add[N<<2],now[N],tot;struct A { ???int num,id,v;}a[N];struct node { ???int l,r;}b[N];bool cmp1(const A &x,const A &y){return x.num<y.num;}bool cmp2(const A &x,const A &y){return x.id<y.id;}bool cmp3(const node &x,const node &y) { ???if(x.r==y.r) return x.l>y.l; ???return x.r<y.r;}void pushdown(int p) { ???if(add[p]) { ???????int d=add[p]; ???????add[ls]+=d; t[ls]+=d; ???????add[rs]+=d; t[rs]+=d; ???????add[p]=0; ???}}void build(int l,int r,int p) { ???t[p]=m-1; ???if(l==r) {return ;} ???int mid=(l+r)>>1; ???build(l,mid,ls); build(mid+1,r,rs);}int query(int l,int r,int x,int y,int p) { ???if(x<=l&&y>=r) return t[p]; ???int mid=(l+r)>>1,re=1<<30; ???pushdown(p); ???if(x<=mid) re=min(re,query(l,mid,x,y,ls)); ???if(y>mid) re=min(re,query(mid+1,r,x,y,rs)); ???t[p]=min(t[ls],t[rs]); ???return re;}void update(int l,int r,int x,int y,int v,int p) { ???if(x<=l&&y>=r) { ???????t[p]+=v; add[p]+=v; ???????return ; ???} ???pushdown(p); ???int mid=(l+r)>>1; ???if(x<=mid) update(l,mid,x,y,v,ls); ???if(y>mid) update(mid+1,r,x,y,v,rs); ???t[p]=min(t[ls],t[rs]);}int main() { ???memset(t,0x3f,sizeof(t)); ???scanf("%d%d",&n,&m); ???int i; ???for(i=1;i<=n;i++) { ???????scanf("%d",&a[i].num); a[i].id=i; ???} ???sort(a+1,a+n+1,cmp1); ???int j=0;a[0].num=1<<30; ???for(i=1;i<=n;i++) { ???????if(a[i].num!=a[i-1].num)j++; ???????a[i].v=j; ???} ???sort(a+1,a+n+1,cmp2); ???int ans=n; ???for(i=n;i>=1;i--) { ???????if(now[a[i].v]) { ???????????b[++tot].l=i+1; ???????????b[tot].r=now[a[i].v]-1; ???????????if(b[tot].l>b[tot].r) tot--,ans--; ???????} ???????now[a[i].v]=i; ???} ???sort(b+1,b+tot+1,cmp3); ???build(1,n,1); ???for(i=1;i<=tot;i++) { ???????int re=query(1,n,b[i].l,b[i].r,1); ???????if(re>=1) { ???????????update(1,n,b[i].l,b[i].r,-1,1); ???????????ans--; ???????} ???} ???printf("%d\n",ans);}BZOJ_1826_[JSOI2010]缓存交换 _线段树+贪心
原文地址：https://www.cnblogs.com/suika/p/8997657.html