bzoj1206 [HNOI2005]虛拟記憶體

​​http://www.elijahqi.win/2018/01/07/bzoj1206-hnoi2005%e8%99%9a%e6%8b%9f%e5%86%85%e5%ad%98/​​​

Description

作業系統中一種重要的存儲管理技術就是虛拟記憶體技術。作業系統中允許程序同時運作，也就是并行。每個程序都有其相對獨立的資料塊（程序運作的過程中将對其進行讀寫操作）。理想的情況下，這些資料塊都應該存放在記憶體中，這樣才能實作高效的讀寫操作。但事實上，記憶體的容量有限，每個程序隻能把一部分資料放在記憶體中，為了解決這個沖突，提出了虛拟記憶體技術。虛拟記憶體技術的基本原理是：對程序而言，記憶體空間是無限大的，程序可以随意地讀寫資料，而對作業系統内部而言，利用外存來模拟擴充的記憶體空間，程序要求通路某個記憶體單元時，交由作業系統處理，作業系統首先在記憶體中查找該單元是否存在，如果存在，查找成功，否則轉入外存查找（一定存在于外存中）。就存儲媒體的實體性質而言，記憶體的通路速度相對于外存要快得多，是以對于每個程序來說作業系統應該把那些通路次數較多的資料存放在記憶體中，而把那些通路次數很少的資料放在外存中。如何選擇記憶體中暫留的資料是一個很值得研究的問題，下面介紹一個記憶體管理中比較常用的算法：記憶體中的資料以頁為基本存儲機關，程序的讀寫操作都針對頁來進行。實際記憶體空間被分割成n頁，虛拟記憶體空間的頁數往往要多得多。某一時刻，程序需要通路虛存編号為P的頁，該算法的執行步驟如下： a. 首先在記憶體中查找，如果該頁位于記憶體中，查找成功，轉d，否則繼續下面的操作； b. 尋找記憶體中是否存在空頁（即沒有裝載任何資料頁的頁面），若有，則從外存中讀入要查找頁，并将該頁送至記憶體中的空頁進行存儲，然後轉d，否則繼續下面的操作； c. 在記憶體中尋找一個通路次數最少的頁面（如果存在多個頁面的通路次數同時為最少，則選取最早讀入資料進入記憶體的那個頁面），從外存中讀入要查找頁，替換該頁。 d. 結束所謂通路次數是指從目前頁面進入記憶體到該時刻被通路的次數，如果該頁面以前進入過記憶體并被其它頁面替換，那麼前面的通路次數不應計入這個時刻的通路次數中。你的任務是設計一個程式實作上述算法。測試資料将會提供m條讀寫記憶體的指令，每條命題提供要求通路的虛拟記憶體頁的編号P。你的程式要求能夠模拟整個m條指令的全部執行過程，所有的指令是按照輸入的先後執行的，最開始的時候記憶體中的n頁全為空。

Input

#include<cstdio>
#include<queue>
#include<map>
#define N 1100000
using namespace std;
int p,n,m,tot,flag[N];
map <int,int> ma;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
} 
inline int read(){
    int x=0;char ch=gc();
    while (ch<'0'||ch>'9') ch=gc();
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}
    return x;
}
struct node{
    int num,happen,dis;//num 輸入順序 happen 通路次數 dis離散化對應的值
    bool operator > (const node &other) const{
        if (happen<other.happen) return false;
        if (happen>other.happen) return true;
        return num>other.num;
    } 
}x;
priority_queue <node,vector<node>,greater<node> >  team;//定義了複雜類型的優先隊列 
int main(){
//  freopen("2318.in","r",stdin);
//  freopen("2318.out","w",stdout);
    n=read();m=read();int ans=0;
    for (int i=1;i<=m;++i){
        p=read();int k=0;
        if (!ma[p]){
            ma[p]=++tot;k=tot;
        }else k=ma[p];
        flag[k]++;
        if (flag[k]>1){ans++;continue;}
        x.happen=1;x.num=i;x.dis=k;
        if (team.size()!=n) {team.push(x);continue;}
        node y=team.top();
        while (y.happen!=flag[y.dis]){
            team.pop();
            y.happen=flag[y.dis];  //修改team中 happen成為真實值 
            team.push(y);
            y=team.top();
        }
        flag[y.dis]=0;team.pop();team.push(x);
    } 
    printf("%d",ans);
    return 0;
}