思路:排序+模拟
由于必须按照优先级访问,所以我们可以按照优先级排序,然后按时间顺序模拟。
假如现在在时间now , 该任务下一个可以访问的时间是time+k∗gap , 需要满足 now+gap∗k>time
所以我们可以求出k=gap(now−time+gap−1) .这是计算机中得到向上取整的方法。而由于k可能为负数,所以我们需要取max(0,k)
最后now=time+gap∗k,迭代完所有景点即可。
P1876.第1题-多多的计划
题目描述
多多制定了一个庞大的旅行计划。具体而言,多多准备去N个景点游玩。它还为每个景点设定了优先级,必须先前往优先级高的景点游玩,然后才能前往优先级低的景点,各个景点优先级互不相同。
同时由于各大景点都十分火爆,多多只能在已预约的第Xi天前往景点i,如果无法按约前往,则只能等过Di天再次前往。即,多多只能在第Xi、Xi+Di、Xi+2Di、...天前去景点i。
多多一天最多游玩一个景点,请问至少需要几天才能完成它的旅行计划。
输入描述
第一行,一个整数N,表示有N个景点。
接下来N行, 每行有三个整数Pi, Xi, Di
- Pi 是景点i优先级,数字越小,表示优先级越高
- Xi 是针对景点i的初次预约时间
- Di 是允许再次前往的天数间隔
1≤N,Pi≤100000.
1≤Xi,Di≤1000.
输出描述
一个整数,表示完成旅行计划的天数
样例
输入
2
1 2 2
2 1 3
输出
4
说明
1号景点优先级最高。
第2天前往1号景点,然后只能在第4天前往2号景点,因此共4天。
样例
输入
3
3 2 3
1 3 2
2 2 2
输出
5