思路:排序+模拟

由于必须按照优先级访问，所以我们可以按照优先级排序，然后按时间顺序模拟。 假如现在在时间now , 该任务下一个可以访问的时间是$time + k * gap$ , 需要满足 $now + gap * k > time$ 所以我们可以求出$k = \frac{(now - time + gap - 1)}{gap}$ .这是计算机中得到向上取整的方法。而由于$k$可能为负数，所以我们需要取$max(0 , k)$

最后$now = time + gap * k$，迭代完所有景点即可。

代码

Python

n = int(input())
arr = []
for i in range(n):
    arr.append(list(map(int , input().split())))
arr.sort(key = lambda x: x[0])
now = 0
for x in arr:
    _ , time , gap = x
    #向上取整
    k = (now - time + gap - 1) // gap
    if k < 0:
        k = 0
    now = time + gap * k
print(now)

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <math.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<tuple<int, int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
        int p, x ,d;
        cin >> p >> x >> d;
        arr[i] = {p, x, d};
    }
    sort(arr.begin(), arr.end(), [](const  tuple<int, int, int>&a, const  tuple<int, int, int>&b) {
        auto [p1, x1, d1] = a;
        auto [p2, x2, d2] = b;
        return p1 < p2;
    });
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        auto [p, x, d] = arr[i];
        if (ans < x) {
            ans = x;
        }
        else {
            int num = (int)ceil((double)(ans - x) / d) * d;
            if (x + num == ans) {
                ans = x + num + d;
            }
            else {
                ans = x + num;
            }
            // ans = x + num;
            // if (d == 1){
            //     ans++;
            // }
        }
    }
    cout << ans << endl;
    return 0;
}

java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ps = new int[n];
        Map<Integer, int[]> map = new HashMap<>();
        for(int i=0; i<n; i++) {
            int p = sc.nextInt();
            int x = sc.nextInt();
            int d = sc.nextInt();
            ps[i] = p;
            map.put(p, new int[]{x, d});
        }

        int start = 0;
        Arrays.sort(ps);
        for(int i=0; i<n; i++) {
            int p = ps[i];
            int x = map.get(p)[0];
            int d = map.get(p)[1];
            if(x > start) start = x;
            else {
                start = x + ((start-x)/d)*d + d;
            }

        }
        System.out.println(start);
    }
}

题目描述

多多制定了一个庞大的旅行计划。具体而言，多多准备去$N$个景点游玩。它还为每个景点设定了优先级，必须先前往优先级高的景点游玩，然后才能前往优先级低的景点，各个景点优先级互不相同。

同时由于各大景点都十分火爆，多多只能在已预约的第$X_i$天前往景点$i$，如果无法按约前往，则只能等过$D_i$天再次前往。即，多多只能在第$X_i$、$X_i+D_i$、$X_i+2D_i$、...天前去景点$i$。

多多一天最多游玩一个景点，请问至少需要几天才能完成它的旅行计划。

输入描述

第一行，一个整数$N$，表示有$N$个景点。

接下来$N$行, 每行有三个整数$P_i$, $X_i$, $D_i$

• $P_i$ 是景点$i$优先级，数字越小，表示优先级越高
• $X_i$ 是针对景点$i$的初次预约时间
• $D_i$ 是允许再次前往的天数间隔

$1 \leq N, P_i \leq 100000$. $1 \leq X_i, D_i \leq 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