大概题意:
N的内存,M的页面,N刚开始为空,M页面表示页面编号从1->M,Q次询问 问需要添加或置换的次数最小是多少。 贪心
思路:
需要一个数据结构存储页面,简写为q有新的元素准备进入的时候,分为三种情况,第一种q情况没满。第二种情况,q满了,看已经在队列里面的数,谁的相同的下一个数离的最远就替换掉谁。第三种情况,q满了,但是新的元素的同值存在。 离得远,i对应的大,根据离得远近,来排列队列里的数,会想到优先队列,大根堆,不是按照数值排序,需要pair<int,int>。 为了判断是第二种还是第三种情况,需要一个bool数组判断是否元素已经存在在堆里。
重点部分:(贪心的维护)
需要维护,每个位置,对应的值,下次出现在哪个位置。
假设是值仅出现一次,那默认为无穷远。(0x3f)now初始化为无穷远。另外一个随便。0或者无穷远。0取不到的。
意思是希望下标就可以引出值对应的下一个位置。i->位置[a[i]]。
位置[a[i]]->下个位置。 数组的下标对应数组的值。
ntx[]下标是位置,值是位置对应的a值的下一个a值的位置。
所以还需要一个now【】下标是a值,值是a值此时的位置。
ntx:从位置对应到值的下一个位置。now从值对应到此时的位置。
都说了是下一个位置,肯定是从大到小遍历。
源代码:
using namespace std;
const int N=5e4+10;
priority_queue<pair<int,int>> qu;//需要把某个元素,和它的下个位置绑定在一起。
int nxt[N],now[N],a[N];
bool st[N];
int n,m,q;
int ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
while(cin>>n>>m>>q){
ans = 0;
memset(nxt,0,sizeof nxt);
memset(now,0x3f,sizeof now);
memset(st,0,sizeof st);
while(qu.size()) qu.pop();//新的开始必须要先重制
for(int i=1;i<=q;i++) cin>>a[i];
for(int i=q;i>0;i--){
nxt[i] = now[a[i]];
now[a[i]] = i;
}
int tmp = 0;//记录重复的数
for(int i=1;i<=q;i++){
if(st[a[i]]) tmp++;//假如数重复了
if(!st[a[i]] && qu.size()<n+tmp){
ans++;
st[a[i]] = 1;
}
else if(qu.size()==n+tmp && !st[a[i]]) {
ans++;
st[qu.top().second] = 0;
qu.pop();
st[a[i]] = 1;
}
qu.push({nxt[i],a[i]});//希望达到的效果是,按照nxt的大小排序,就算a值相同,再次读入也是大的更有可能为顶。放在循环语句外面,意思是三种情况都要推进元素。
}
cout<<ans<<"\n";
}
}