goj LRU页面置换算法
Problem Description:
sss操作系统没听课, 这周的操作系统作业完全不会, 你能帮他写出来吗, 以下是操作系统老师的实验说明: LRU算法解释: LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 LRU的实现（需要“堆栈”支持）: 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号.
Input:
多组输入 每组数据第一行为n(1<=n<=100),n为页面栈的大小, m(1<=m<=500000), m为需要访问的页面序列长度, 第二行为访问页面序列a1~am (0<=ai<=1000)
Output:
输出一行, 最后栈内的元素(从栈底开始输出)
Sample Input:
5 11 4 7 0 7 1 0 1 2 1 2 6
Sample Output:
7 0 1 2 6
解题思路：结合LRU置换算法的定义举个栗子：假设现有一进程所访问的页面序列为：4，7，0，7，1，0，1，2，1，2，6。随着进程的访问，栈中页面号的变化情况如图所示。在访问页面6时发生了缺页，此时页面4是最近最久未被访问的页，应将它置换出去。此题直接暴力模拟即可。正确做法：双向链表+哈希表！
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn=500005; 5 int n,m,x,cnt,stk[110],pos[maxn]; 6 int main(){ 7 while(cin>>n>>m){ 8 cnt=0;memset(pos,0,sizeof(pos));//标记页面在栈中的位置 9 while(m--){ 10 cin>>x; 11 if(pos[x]){//栈中已出现x，将x提到栈顶，剩下的页面往下移 12 for(int i=pos[x];i<cnt;++i)stk[i]=stk[i+1],pos[stk[i]]=i; 13 stk[cnt]=x,pos[x]=cnt; 14 } 15 else{//x未出现 16 if(cnt!=n)stk[++cnt]=x,pos[x]=cnt;//栈未满则直接添加 17 else{//栈满，移去最久未使用的页面，将x放栈顶 18 for(int i=1;i<n;++i)stk[i]=stk[i+1],pos[stk[i]]=i; 19 stk[n]=x,pos[x]=n; 20 } 21 } 22 } 23 for(int i=1;i<=cnt;++i)cout<<stk[i]<<(i==cnt?' ':' ');//输出当前栈中的页面号 24 } 25 return 0; 26 }