A-2 LRU-K(攀拓(PAT)- 程序设计(甲级)2023年春季考试仿真卷)

这篇具有很好参考价值的文章主要介绍了A-2 LRU-K(攀拓(PAT)- 程序设计(甲级)2023年春季考试仿真卷)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

A-2 LRU-K

分数 25

作者 陈越

单位 浙江大学

Least Recently Used (LRU) cache scheme is to remove the least recently used frame (the one hasn't been used for the longest amount of time) when the cache is full and a new page is referenced which is not there in cache.

LRU-K is a variant of the LRU algorithm, where K represents the number of recent uses. LRU can be considered as LRU-1. Unlike LRU, the LRU-K requires the maintenance of two different queues (for historical access and cache). The data in the historical access queue is not moved to the cache queue until the data is hit K times.

For example, assuming that the length of both queues is 5, and the memory is initialized to be empty. LRU-2 is used to process the data sequence in order: 9,5,6,7,8,3,8,9,5,9,8,3,4,7,5,6. The changes of the historical access queue and the cache queue are shown in the following table:

Data Access Historical Aaccess Queue Cache Queue
9,5,6,7,8 9,5,6,7,8 Empty
3 5,6,7,8,3 Empty
8 5,6,7,3 8
9 5,6,7,3,9 8
5 6,7,3,9 8,5
9 6,7,3 8,5,9
8 6,7,3 5,9,8
3 6,7 5,9,8,3
4 6,7,4 5,9,8,3
7 6,4 5,9,8,3,7
5 6,4 9,8,3,7,5
6 4 8,3,7,5,6

Your job is to implement this LRU-K cache scheme.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 positive integers: K (≤5), N (≤104) and M (≤105) which are the number of hits for cache, the size of the queues (assuming both queues have the same size) and the number of referenced page ID's. Then M referenced page ID's are given in the next line. A page ID is a number in the range [1,2×104]. All the numbers in a line are separated by a space.

Output Specification:

For each test case, output in the first line the page ID's in the historical access queue, and in the second line, those in the cache queue. The ID's are ordered from front to rear of each queue. All the numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line. In case that a queue is empty, output - in a line instead.

Sample Input 1:

2 5 17
9 5 6 7 8 3 8 9 5 9 8 3 4 7 5 6 9

Sample Output 1:

4 9
8 3 7 5 6

Sample Input 2:

3 5 10
9 5 6 7 8 3 8 9 5 9

Sample Output 2:

7 3 8 5 9
-

 
 * 解题思路,因为中间涉及值的查找操作,还有删除操作,但是查询以及删除
 * 操作都可能在序列中间进行,所以不能用优先队列,优先队列只能在队首
 * 进行删除以及查找可以在O(log n)的时间内完成,此时我们就可以想到set
 * 或者map,他们在任何位置进行删除以及查找的时间复杂度都是O(lon n);
 *
 * 由于是LRU算法,所以我们需要两个值来对一个页面进行记录,即页面编号id,
 * 最近页面使用的时间代表,时间代表越大,则表示最近刚使用完;因此可以
 * 定义一个结构体用set来解决;
 *
 * 最先使用的优先对列,可是有几个样例过不去(TLE),现在想想也能想明白;
文章来源地址https://www.toymoban.com/news/detail-478126.html

/**
 * 解题思路,因为中间涉及值的查找操作,还有删除操作,但是查询以及删除
 * 操作都可能在序列中间进行,所以不能用优先队列,优先队列只能在队首
 * 进行删除以及查找可以在O(log n)的时间内完成,此时我们就可以想到set
 * 或者map,他们在任何位置进行删除以及查找的时间复杂度都是O(lon n);
 * 
 * 由于是LRU算法,所以我们需要两个值来对一个页面进行记录,即页面编号id,
 * 最近页面使用的时间代表,时间代表越大,则表示最近刚使用完;因此可以
 * 定义一个结构体用set来解决;
 * 
 * 最先使用的优先对列,可是有几个样例过不去(TLE),现在想想也能想明白;
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

struct Infor
{
    int id, flag;
    bool operator < (const Infor& a) const
    {
        //先按照flag从小到大,如果flag相等则按照id从小到大排序
        //请注意,比较关系一定要写完全,不能只写成flag < a.flag;
        //当b.flag == a.flag 时,set就不知道哪个在前,哪个在后,
        //或者干脆不知道 a 是否等于 b,因为 a.flag 确实不等于b.flag啊,
        //你没有显示的告诉id 和 a.id 的关系
        if(flag != a.flag) 
            return flag < a.flag;
        else 
            return id < a.id;
    }
};
const int N = 2e4+10;
set<Infor> cache, hist; 
int idx[N]; //最近使用页面的时间代表
int cnt[N]; //页面在history队列中被使用的次数
int k, n, m;

//输出结果
void Print(set<Infor> st)
{
    if(st.empty())  puts("-");
    else
    {
        bool spa = false;
        for(auto ele : st)
        {
            if(spa) cout << ' ';
            else spa = true;
            cout << ele.id;
        }
        cout << endl;
    }
}

int main()
{
    cin >> k >> n >> m;
    
    for(int i=0; i<m; ++i)
    {
        int id;
        cin >> id;
        
        //id页面在cache中
        if(cache.find({id, idx[id]}) != cache.end())
        {
            //将id加在cache的末尾
            cache.erase({id, idx[id]});
            idx[id] = i;
            cache.insert({id, idx[id]}); 
        }
        else
        {
            //id在hist中
            if(hist.find({id, idx[id]}) != hist.end())
            {
                ++cnt[id];
                
                //id或者加在hist末尾,或者加在cache末尾(当次数达到k)
                hist.erase({id, idx[id]});
                idx[id] = i;
                
                if(cnt[id] == k)
                {
                    //id加在cache末尾(当次数达到k)
                    cache.insert({id, idx[id]});
                    cnt[id] = 0;
                    if(cache.size() > n)
                        cache.erase(cache.begin()); 
                    //超过容量,去掉“队首”的页面
                }
                else
                    //id加在hist末尾
                    hist.insert({id, idx[id]});
            }
            else //id不在hist中,id第一次被调入hist中
            {
                ++cnt[id];
                idx[id] = i;
                hist.insert({id, idx[id]});
               
                } if(hist.size() > n)
                {
                    int id = hist.begin()->id;;
                    hist.erase(hist.begin());
                    cnt[id] = 0;
            }
        }
    }
            
    
    Print(hist);
    Print(cache);
    
    return 0;
}

到了这里,关于A-2 LRU-K(攀拓(PAT)- 程序设计(甲级)2023年春季考试仿真卷)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 1114 Family Property (PAT甲级)

    This time, you are supposed to help us collect the data for family-owned property. Given each person\\\'s family members, and the estate(房产)info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate. Input Specification: Each input file contains one test case. For each case, the fir

    2024年02月06日
    浏览(51)
  • 1028 List Sorting (PAT甲级)

    Excel can sort records according to any column. Now you are supposed to imitate this function. Input Specification: Each input file contains one test case. For each case, the first line contains two integers N (≤105) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, eac

    2024年02月15日
    浏览(41)
  • 1072 Gas Station (PAT甲级)

    A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range. Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendatio

    2024年02月09日
    浏览(42)
  • 1021 Deepest Root (PAT甲级)

    1021. Deepest Root (25)-PAT甲级真题(图的遍历,dfs,连通分量的个数)_柳婼的博客-CSDN博客 柳婼的解法在这里,两次dfs,还是挺好玩的。 我的解法比较暴力,就是先用并查集算连通分量(这个其实还是dfs来算会更方便),如果只有一个连通分量,那deepest root一定在仅有一条arc的

    2024年02月15日
    浏览(35)
  • 1111 Online Map (PAT甲级)

    这道题我读题不仔细导致踩了个大坑,一个测试点过不了卡了好几个小时:第二个dijkstra算法中,题目要求是“In case the fastest path is not unique, output the one that passes through the fewest intersections”,我却想当然地认为在fastest path is not unique的时候,判断标准是最短距离…… Input our

    2024年02月07日
    浏览(43)
  • pat甲级 1022 Digital Library

    A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID\\\'s. Input Specification: Each inp

    2024年04月15日
    浏览(36)
  • 1083 List Grades (PAT甲级)

    Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of which the grades are in a given interval. Input Specification: Each input file contains one test case. Each case is given in the following format: where  name[i]  and  ID[i

    2024年02月08日
    浏览(49)
  • PAT甲级图论相关题目

    PAT甲级图论相关题目: 分数 25 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some o

    2024年01月21日
    浏览(54)
  • PAT 甲级【1007 Maximum Subsequence Sum】

    本题是考察动态规划与java的快速输入: max[i]表示第i个结尾的最大的连续子串和。b begin[i]表示第[begin[i],i]为最大和的开始位置 超时代码: 未超时: 能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠。 具有最优子结构也可能是适合用贪心的

    2024年02月08日
    浏览(41)
  • 1074 Reversing Linked List (PAT甲级)

    Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6. Input Specification: Each input file contains one test case. For each case, the first line

    2024年02月09日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包