Least Recently Used，即最近最少使用，常用於頁面置換，是為虛擬頁式存儲管理服務的。 關於作業系統的記憶體管理，如何節省利用容量不大的記憶體為最多的進程提供資源，一直是研究的重要方向。而記憶體的虛擬存儲管理，是現在最通用，最成功的方式—— 在記憶體有限的情況下，擴展一部分外存作為虛擬記憶體，真正的記憶體只存儲當前運行時所用得到信息。這無疑極大地擴充了記憶體的功能，極大地提高了計算機的並發度。虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，記憶體中只存放當前所需頁面，其餘頁面放入外存的管理方式。 然而，有利就有弊，虛擬頁式存儲管理增加了進程所需的記憶體空間，卻也帶來了運行時間變長這一缺點：進程運行過程中，不可避免地要把在外存中存放的一些信息和記憶體中已有的進行交換，由於外存的低速，這一步驟所花費的時間不可忽略。因而，採取儘量好的算法以減少讀取外存的次數，也是相當有意義的事情。
為了儘量減少與理想算法的差距，產生了各種精妙的做法，最少使用頁面置換算法便是其中一個。Least Recently Used演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比記憶體速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最久未使用的那個頁面調出記憶體。
以上圖為例，在容量只有3的記憶體使用，依序分別使用 1 6 4 2 5 等頁面，而在頁面4要使用時發現不夠放了，因此將最久未使用的頁面1調出記憶體，再放入頁面4
第一行有一個整數 $T$，代表接下來有 $T$ 筆測資
每筆測資第一行有二個整數 $N$、$K$，分別代表 $N$ 個使用的頁面以及記憶體容量大小為 $K$
第二行有 $N$ 個整數 $P_i$ ，分別代表每次使用時的頁面編碼 $P_i$
$ 1 \le T \le 1000$
$1 \le N \le 2 \cdot 10^5$
$1 \le K \le 2 \cdot 10^5$
$1 \le P_i \le 10^9$
保證 $T$ 筆測資的 $N$ 加起來不超過 $10^6$
對於 40% 測資無重複頁面 $P_i$
對於 60% 測資無特殊限制
輸出共 $T$ 行
每行有 $N$ 個整數，為每次使用頁面時所被調出記憶體的頁面
如未有頁面被調出則輸出 $-1$
2 5 3 1 6 4 2 5 3 3 5 5 5
-1 -1 -1 1 6 -1 -1 -1
不公開 測資點#0 (10%): 2.0s , <10M
不公開 測資點#1 (10%): 2.0s , <10M
不公開 測資點#2 (10%): 2.0s , <10M
不公開 測資點#3 (10%): 2.0s , <10M
不公開 測資點#4 (10%): 2.0s , <10M
不公開 測資點#5 (10%): 2.0s , <10M
不公開 測資點#6 (10%): 2.0s , <10M
不公開 測資點#7 (10%): 2.0s , <10M
不公開 測資點#8 (10%): 2.0s , <10M
不公開 測資點#9 (10%): 2.0s , <10M
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||