题解 | #[JSOI2010]缓存交换#

[JSOI2010]缓存交换

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

首先这道题是用贪心加优先队列解决,优先队列用来降低算法复杂度维护一个大根堆
此题主要思想为替换策略是每次替换最远出现的缓存块
大根堆用来维护缓存中缓存块下一次出现的时间
此外需要维护一个next数组,用来寻找当前元素下一次出现的下标
所以需要一个mp数组记录当前元素上一次出现的下标 从后往前遍历得到next数组

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务