东东要去他家路口的公交车站等車!!!
东东从家出发需要 d 分钟到达公交站台。
已知有 n 班公交车第 i 路公交车在 a_i 分钟到达公交站台,随后每 b_i 分钟会有该路公交车
东东想着他要迟到了!!!可恶!!!要迟到了!!于是他看见了一辆公交车来了,立马跳上了这辆"他见到的"第一辆公交车
东东上车后发现叻一个问题!!这不是去幼儿园的车!!!!可惜车门已经焊死。
那么问题来了东东上的是第几路车
接下来n行,每行两个数字a_i和b_i(1≤a_i,b_i≤1e5)分别为该路公交首辆车到达的时间和两辆车之间的发车间隔
如果有多种可能,输出一种
东东所上车的公交车的路线编号
这个样例看嘚我一脸懵,我一开始没反应过来咋回事儿结果发现是:我到了车站之后如果有车我就上,如果没有车我就等着等到最早的车来到位置,当然题目里说了只需要一辆车就可以不是全写出来。其实这个问题可以再简化一下如果你到了车站马上有车那就意味着等待时间為0,这样就把问题合并起来了所以我们要求的就是在刚刚超过或者等于到车站的时间时最小的那一个,这样到了之后就可以等最小的时間然后遇到最早来的车
那么对于每一辆车来说就要求出刚刚超过(或者等于)到车站的时间的时间了,while里面刚好在退出的时候不满足要求退出的时候是刚刚好大于等于到车站的时间,所以满足前面的分析
然后就可以求出最小时间了,记录下最小时间的标号