机试

4月8号投的暑期实习，5.13被捞机试（隔太久了俺都快把这事忘了），5.14开考。一共三道题，分别是100分，200分，300分（题目的完整描述不记得了，但记得大致细节）第一题（100分）写一个数据结构，能执行以下操作：（1）插入一个id-优先级的键值对。例子："+ 1 10"，加号代表插入操作，1 10代表ID为1的优先级为10（2）按优先级降序（优先级相同的时候id升序）提取前k个键值对的id，提取之后的键值对移除掉。例子："- 2"，"-" 代表提取操作，二代表提取优先级最大的前两个，并输出（3）更改指定id的优先级，执行更改操作的时候，先前移除掉的键值对全部重新插入。例子： "= 1 20""=" 代表更新操作，表示把ID为1的优先级重新设置为20输入样例：7 （代表执行七次操作）+ 1 10+ 2 5+ 3 9- 2= 2 20- 1- 1输出样例：1 323（这题直接无脑写的，用一个哈希表存，每次执行提取操作的时候转移到vector里排序，过了85%的样例）第二题（200分）动态规划+图（还挺简单的直接通过）输入n，给一个n×n的矩阵map，map[i][j] 代表坐标为（i，j）处的高度，一个人从map[0][0]出发，可以从矩阵右边任意处离开。人通过map[i][j]处需要消耗map[i][j]点体力，他每次只能往左map[i][j+1]或者往下map[i+1][j]走一格，如果两格高度差大于1就会摔死。求人离开时消耗最少的体力，如果没有可离开的路径返回-1，参数违法返回-2。输入样例：31 2 35 5 56 6 6输出：6（移动路径1-2-3）第三题（300分）（没写，前俩整完就剩个20分钟了这题就记了下题目）背景是灾区救援，输入两行数据，第一行表示车队的物资数，第二行表示领物资的人所需要的物资数。每次从车里领物资的时候，从领物资队列里，寻找总值小于等于它的最长连续子序列，然后给他们分配物资。如果找不到子序列，把该车的物资累积到下个车进行分配。输出分配次数和没有领物资的人数。输入样例：8 2 5 4 72 3 6 1 2 1 1 7输出4 1第一轮：物资数是8， 可分配给最长连续子序列1 2 1 1分配完后物资：2 5 4 7领物资的队列：2 3 6 7第二轮：物资数是2，可分配给子序列2分配完后物资：5 4 7领物资的队列：3 6 7第三轮：物资数是5，可分配给子序列3分配完后物资：4 7领物资的队列：6 7第四轮：物资数是4，无法分配，累计到下一轮分配第五轮：物资数是 4+7=11，可分配给子序列7分配完物资：（无了）领物资的队列：6因此输出：4 1总共进行过4次分配，余下一人领不到物资