最佳页面置换算法

https://ac.nowcoder.com/acm/problem/20185

import heapq

class Solution:
    def __init__(self, mem_id_list: List[int], capacity: int):
        self.mem_id_list: list[int] = mem_id_list
        self.capacity = capacity
        # 记录cache中已有的内存编号
        self.cache_map: dict[int, bool] = {}
        # next数组
        self.next: list[int] = [0] * len(mem_id_list)
        # 堆用于记录下次出现的下标
        self.heap: list[int] = []

    def init_next(self, length):
        mp = {}

        # 从后往前记录
        for idx in range(length - 1, -1, -1):
            mem_id = self.mem_id_list[idx]

            if self.mem_id_list[idx] in mp:
                self.next[idx] = mp[mem_id]
            else:
                self.next[idx] = length + 100
            # 记录
            mp[mem_id] = idx

    def cache(self, mem_id_list: List[int], capacity: int) -> int:
        # 最佳页面置换算法：当需要弹出缓存，确认当前cache中的内存编号和未来要访问的内存的距离，找到距离最远的，淘汰掉，最近的保留

        self.mem_id_list = mem_id_list
        miss_cnt = 0

        length = len(mem_id_list)

        self.init_next(length)
        num = 0

        for i, mem_id in enumerate(mem_id_list):
            if self.cache_map.get(i, False) == False:
                miss_cnt += 1

                if num < capacity:
                    num += 1
                    self.cache_map[self.next[i]] = True
                    heapq.heappush(self.heap, -(self.next[i]))
                else:
                    self.cache_map[-self.heap[0]] = False
                    heapq.heappop(self.heap)
                    self.cache_map[self.next[i]] = True
                    heapq.heappush(self.heap, -(self.next[i]))
            else:
                self.cache_map[self.next[i]] = True
                heapq.heappush(self.heap, -(self.next[i]))

        return miss_cnt
    
if __name__ == "__main__":
    while True:
        try:
            access_times, capacity = list(map(int, input().split(" ")))
            mem_id_list: list[int] = list(map(int, input().split(" ")))

            print(Solution(mem_id_list, capacity).cache(mem_id_list, capacity))
        except:
            break