配方制作-研发_网易互娱笔试题

明明最近迷上了《明日之后》这款游戏。在这款游戏中有一个配方制造系统，玩家可以利用手中的资源和材料，来制造武器和道具。例如，玩家如果需要制造一个小木柜，需要3块木板，而制造一块木板，又需要120个木头和2个小树枝，并且需要走到建筑加工台前制作。而采集木头和小树枝又需要一定的时间。

玩了一段时间之后，明明开始好奇在游戏中做什么最花时间。虽然游戏中已经有标明每个物品的制造时间，但是明明更想通过自己的游戏经历来统计实际需要的时间。明明根据自己的操作，记录下了自己游戏中每个操作事件的开始和结束时间，按时间顺序汇总成了一张表，如下所示：

从上表可以看出，“制造1个小木柜”这个操作，总共用时2000-1=1999秒时间，其中包含两部分：制造3块木板的耗时（1000-5=995秒）和自身的耗时（1999-995=1004秒）。同样的，制造3块木板的995秒耗时中，也包括3部分：收集360个木头的耗时（20-10=10秒）、收集6个小树枝的耗时（40-25=15秒）以及自身耗时（995-10-15=970秒）。在这些操作当中，“制造1个小木柜”自身耗时1004秒，是所有操作中自身耗时最多的一个操作。

明明想知道自己做的这些操作中，哪个操作自身所花的时间是最多的。给出这张事件记录表，你可以帮明明计算一下吗？

数据范围：输入数据组数满足 $1 \le t \le 100 \$ ，每组数组中操作数满足 $1 \le n \le 100000 \$ ，操作中的数都满足 $0 \le val \le 2^{30} \$ 、时间结束和开始信息满足 $0 \le s \le 1 \$
进阶：空间复杂度 $O(n)\$ ，时间复杂度 $O(n) \$

输入中包含多组数据。输入的第一行是一个整数T(T<=100)，表示后续有多少组测试数据。

每组测试数据第一行是一个整数N(N<=100000)，表示记录的行数。随后是N行记录，每行包括3个整数t（030）、e(030)、s(0或1)，表示事件的时间、事件的id，以及开始或结束信息（0表示开始，1表示结束）。这些记录按照时间先后顺序给出，任意两行的时间均不相同。保证任意一个事件仅出现一次开始和一次结束，且开始时间在结束之前。保证子任务一定先于父任务结束。

T=int(input().strip()) for t in range(T): #有T组测试数据 N=int(input().strip()) #该组测试数据有N行 D={} #D保存各个事件ID以及其自身耗时 A=[] parent_list=[] #parent_list保存各个事件的父活动 Tree={} #Tree保存事件父子树(父亲ID以及其各个孩子ID) for n in range(N): tmp=list(map(int,input().strip().split())) if tmp[2]==1: #遇到1出栈 if len(A)>0 and A[-1][-1]==0: t=A[-1] A.pop() D[tmp[1]]=tmp[0]-t[0] #计算各个事件的自身耗时 else: A.append(tmp) #遇到0入栈 if len(A)>=2: parent=A[-2][1] #父亲 child=A[-1][1] #孩子 if parent not in parent_list: parent_list.append(parent) Tree[parent]=[child] else: Tree[parent]=Tree[parent]+[child] for t in Tree: for i in range(len(Tree[t])): D[t]=D[t]-D[Tree[t][i]] #父活动的总耗时=自身耗时-所有孩子的自身耗时 sd=sorted(D) #确保小id在前 maxT=0 for k in range(len(sd)): if D[sd[k]]>maxT: maxT=D[sd[k]] index=sd[k] print(index)

配方制作-研发

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题