Description
In a computer, the CPU can only exchange data directly with the cache. When the required memory unit is not in the cache, the data needs to be transferred from the main memory into the cache. At this point, if the Cache capacity is full, one must be deleted from it first.
For example, the current Cache capacity is 3, and there are memory units numbered 10 and 20. At this point, the CPU accesses the main memory unit numbered 10, and Cache hits.
Next, the CPU accesses the main memory unit numbered 21, so it only needs to move the main memory unit into the Cache, resulting in a missing (Cache Miss).
Next, the CPU accesses the main memory unit numbered 31, which must be replaced by a block from the Cache to move the main memory unit numbered 31 into the Cache, assuming that we remove the main memory unit numbered 10.
Then, the CPU accesses the main memory unit numbered 10 again, causing another missing. We see that if we delete other units in the last deletion, we can avoid the loss of this visit.
In modern computers, LRU (least recently used) algorithms are often used for Cache scheduling -- but as you can see from the previous example, this is not the optimal algorithm.
For a fixed-capacity empty Cache and several consecutive main memory access requests, Congcong wants to know how to change the correct main memory unit every time a Cache is missing in order to achieve the minimum number of Cache missing.
Input
The first line of the input file contains two integers N and M (1<=M<=N<=100,000), representing the number of main memory accesses and the capacity of Cache, respectively.
The second line contains N positive integers separated by spaces, giving the number of each main memory block (no more than 1,000,000,000) in the order of access requests.
Output
Output a line to minimize the number of Cache missing times.
Sample Input
6 2
1 2 3 1 2 3
Sample Output
4
HINT
Unit 3 is replaced by Cache at the fourth missing.
Title Solution
Dispersion and greed
Let the next identical unit at position I be nxt[i], if not nxt[i]=n+1
That must be the biggest nxt[i] pop-up ever.
Then you can build a deletable heap and maintain nxt[i]
And then I did it casually.
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct LSnode{int y,p;}w[110000];
bool cmp(LSnode n1,LSnode n2){return n1.y<n2.y;}
int pla[110000];
struct node
{
int pla;
friend bool operator <(node n1,node n2){return n1.pla<n2.pla;}
};
struct heap
{
priority_queue<node> A,B;
void push(node x){A.push(x);}
void pop()
{
node tx,ty;
tx=A.top();
if(B.size())ty=B.top();
while(tx.pla==ty.pla && B.size()){A.pop();B.pop();tx=A.top();ty=B.top();}
A.pop();
}
void erase(node x){B.push(x);}
node top()
{
node tx,ty;
tx=A.top();
if(B.size())ty=B.top();
while(tx.pla==ty.pla && B.size()){A.pop();B.pop();tx=A.top();ty=B.top();}
return A.top();
}
}q;
int nxt[110000],las[110000];
int n,m,col[110000];
bool vis[110000];
int main()
{
// freopen("swap10.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i].y),w[i].p=i;
sort(w+1,w+1+n,cmp);
int tt=1;col[w[1].p]=1;
for(int i=2;i<=n;i++)
{
if(w[i].y!=w[i-1].y)tt++;
col[w[i].p]=tt;
}
memset(las,-1,sizeof(las));
for(int i=n;i>=1;i--)
{
if(las[col[i]]==-1)nxt[i]=n+1,las[col[i]]=i;
else nxt[i]=las[col[i]],las[col[i]]=i;
}
memset(vis,false,sizeof(vis));
int ans=0,cnt=0,beg=-1;
for(int i=1;i<=n;i++)
{
if(!vis[col[i]])
{
if(cnt==m){beg=i;break;}
vis[col[i]]=true;
ans++;cnt++;
node tmp;tmp.pla=nxt[i];
q.push(tmp);
}
else
{
node tmp;
tmp.pla=i;q.erase(tmp);
tmp.pla=nxt[i];q.push(tmp);
}
if(cnt==m){beg=i+1;break;}
}
if(beg==-1)printf("%d\n",ans);
else
{
for(int i=beg;i<=n;i++)
{
if(!vis[col[i]])
{
vis[col[i]]=true;ans++;
node tmp;
tmp=q.top();
if(tmp.pla!=n+1)vis[col[tmp.pla]]=false;
q.pop();
tmp.pla=nxt[i];
q.push(tmp);
}
else
{
node tmp;
tmp.pla=i;q.erase(tmp);
tmp.pla=nxt[i];q.push(tmp);
}
}
printf("%d\n",ans);
}
return 0;
}