首页 > 试题广场 >

配方制作-研发

[编程题]配方制作-研发
  • 热度指数:1243 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解


明明最近迷上了《明日之后》这款游戏。在这款游戏中有一个配方制造系统,玩家可以利用手中的资源和材料,来制造武器和道具。例如,玩家如果需要制造一个小木柜,需要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秒,是所有操作中自身耗时最多的一个操作。

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


数据范围:输入数据组数满足 ,每组数组中操作数满足 ,操作中的数都满足 、 时间结束和开始信息满足
进阶:空间复杂度 ,时间复杂度

输入描述:

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

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




输出描述:

对于每一组测试数据,输出一个整数,表示自身所花时间最多的事件id。如果有多个满足条件的事件,则输出事件id最小的那个。

示例1

输入

1
8
1 1 0
5 2 0
10 3 0
20 3 1
25 4 0 
40 4 1
1000 2 1
2000 1 1

输出

1

这道题你会答吗?花几分钟告诉大家答案吧!