首页 > 试题广场 >

关联容器map设计

[编程题]关联容器map设计
  • 热度指数:763 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 48M,其他语言96M
  • 算法知识视频讲解
关联容器map保存<key, value>数据,能通过key快速存储或查找记录请设计一个map,能够满足以下要求:
1. map的容量size是一个固定值N,即map最多保存N个<key, value>记录
2. map insert一个<key, value>前,首先判断这个key是否已经在map中存在:
   1) 如果存在:记这个已存在的记录为<key, old_value>,若old_value<value,则old_value更新为value;否则,不做更新
   2) 如果不存在:
       若size<N,则执行map的insert,保存这个<key, value>,且size+=1;
       若size==N,先淘汰掉一个更新时间最早的记录,再执行map的insert,保存这个<key, value>,size保持为N不变。
说明:记录的更新时间默认为其被insert进map的时间,之后的某一时刻T,如果这个记录的value被更新,那么,该记录的更新时间就变为T。

输入描述:
第一行是map的最大size N(N<=200000),之后每一行都为"Key Value",其中Key为一个字符串(长度<16),Value为无符号整数(unsigned int),Key和Value之间用空格分隔。


输出描述:
输出为map insert的过程中被淘汰掉的记录(不输出value被更新的记录),每行为"Key Value", 和输入文件的"Key Value"格式相同。
示例1

输入

2
10_123_50_A0 1566918054
10_123_50_A1 1566918054
10_123_50_A1 1566918055
10_123_50_A3 1566918055
10_123_50_A4 1566918056

输出

10_123_50_A0 1566918054
10_123_50_A1 1566918055

备注:
1.程序首先从标准输入读入第1行,取得map的size大小N,并以N为参数初始化或者构造map;
2.然后再逐行读取标准输入,依次insert进map,在insert过程中,如果发生淘汰map中已有记录的情况,就把这个被淘汰的记录输出到标准输出。