Operating System（贪心、堆）
链接：https://ac.nowcoder.com/acm/problem/15688
来源：牛客网
题目描述
在学习Operating System的过程中，Glory遇到了这样一个问题，现在有一个大小为可以容纳N个页面的内存，硬盘内的内容被分成M个页面，用1~M来标识，一开始内存里没有任何页面，接下来用户会请求Q个页面，你需要设计一个置换算法，使得缺页发生的次数最少。缺页是指用户请求某个编号的页面，但这个页面没有在内存中的情况。发生缺页之后，你必须要把硬盘内对应的页面调入内存中，如果内存已满，你需要置换掉当前内存中的某个页面。
输入描述:
多组数据，请处理到输入结束。
每组数据，第一行为三个整数N，M，Q （0 < N，M，Q <= 50000）
接下来一行Q个数，表示用户请求的页面编号。
输出描述:
对于每组数据，输出一个数，表示最少的缺页次数。
示例1
输入
1 2 3 5 2 3 1 2 1 2 3 3 4 5 4 3 2 1 4 3
输出
3 4
直接模拟OS最佳置换算法就行
1 #include <bits/stdc++.h> 2 typedef long long LL; 3 #define pb push_back 4 #define mst(a) memset(a,0,sizeof(a)) 5 const int INF = 0x3f3f3f3f; 6 const double eps = 1e-8; 7 const int mod = 1e9+7; 8 const int maxn = 1e5+10; 9 using namespace std; 10 11 int a[maxn]; 12 queue<int> qe[maxn]; //记录每个数所在位置下标 13 set<int> st; //当前内存 14 15 int main() 16 { 17 #ifdef DEBUG 18 freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout); 19 #endif 20 21 int n,m,q; 22 while(~scanf("%d %d %d",&n,&m,&q)) 23 { 24 st.clear(); 25 for(int i=1;i<=q;i++) 26 { 27 scanf("%d",&a[i]); 28 qe[a[i]].push(i); 29 } 30 int ans = 0; 31 for(int i=1;i<=q;i++) 32 { 33 if(st.count(a[i])) qe[a[i]].pop(); 34 else if(st.size()<n) 35 { 36 st.insert(a[i]); 37 qe[a[i]].pop(); 38 ans++; 39 } 40 else 41 { 42 int pos = 0, t = 0; 43 for(auto it : st) 44 { 45 if(qe[it].empty()) 46 { 47 t = it; 48 break; 49 } 50 if(qe[it].front()>pos) 51 { 52 pos = qe[it].front(); 53 t = it; 54 } 55 } 56 st.erase(t); 57 st.insert(a[i]); 58 qe[a[i]].pop(); 59 ans++; 60 } 61 } 62 printf("%d\n",ans); 63 } 64 65 return 0; 66 }
另一种用堆写的：
1 #include <bits/stdc++.h> 2 typedef long long LL; 3 #define pb push_back 4 #define mst(a) memset(a,0,sizeof(a)) 5 const int INF = 0x3f3f3f3f; 6 const double eps = 1e-8; 7 const int mod = 1e9+7; 8 const int maxn = 1e5+10; 9 using namespace std; 10 11 int a[maxn]; 12 int Next[maxn]; //Next[i]记录与当前a[i]相同值的下一个点所在的下标 13 int Last[maxn]; //Last[a[i]]记录与当前a[i]相同值的下一个点所在的下标 14 int vis[maxn]; //vis记录当前值是否在内存中 15 priority_queue<pair<int,int> > qe; //first是Next,second是a[i]的值 16 17 int main() 18 { 19 #ifdef DEBUG 20 freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout); 21 #endif 22 23 int n,m,q; 24 while(~scanf("%d %d %d",&n,&m,&q)) 25 { 26 memset(Last,INF,sizeof(Last)); 27 memset(vis,0,sizeof(vis)); 28 while(!qe.empty()) qe.pop(); 29 for(int i=1;i<=q;i++) 30 scanf("%d",&a[i]); 31 for(int i=q;i>=1;i--) //从后往前借助Last求出Next 32 { 33 Next[i] = Last[a[i]]; 34 Last[a[i]] = i; 35 } 36 int num = 0; //当前qe中有多少个不重复的a[i] 37 int ans = 0; 38 for(int i=1;i<=q;i++) 39 { 40 if(!vis[a[i]]) 41 { 42 if(num==n) //当前装不下时,删除离它下一个一样的点的距离最远的点 43 { 44 vis[qe.top().second] = 0; 45 qe.pop(); 46 } 47 else num++; 48 ans++; 49 vis[a[i]] = 1; 50 } 51 qe.push({Next[i],a[i]}); 52 } 53 printf("%d\n",ans); 54 } 55 56 return 0; 57 }
-
原文链接: https://www.cnblogs.com/jiamian/p/13254255.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/363029
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
