菊厂8.31第三题

某电动车续航1000km，时速100kmph，从A前往B，然后中途有N个充电站，每个充电站充电固定1h，返回最短耗时，如果不能到达，则返回-1.
0<=D<=1E6，且D%100==0
0<=N<=1E4
输入
第一行：表示甲乙两城距离D；
第二行：沿途充电站个数N；
第三行：每行两个数据，分别表示充电站距离A的距离和充电的排队时间。
输出
最短耗时。

#include <bits/stdc++.h>
using namespace std;
int main() {
    double D, N;
    // 为避免误差，所有数字按double处理
    int d, t;
    int duration = 1000, velocity = 100;
    cin >> D;
    cin >> N;
    vector> station(N, vector(2));
    for (int i = 0; i < N; i++) {
        cin >> station[i][0] >> station[i][1];
    }
    if (D <= duration) {
        printf("%d\n", D / velocity);
        return 0;
    }
    if (station.empty() || station[0][0] > D) {
        printf("%d\n", -1);
        return 0;
    }
    sort(station.begin(), station.end(), [](const auto &l, const auto &r){
        return l[0] < r[0];
    });
    // dp[i] 表示到达第i个站最小耗时，把起点和终点也当作站加入
    vector dp(N + 1, INT_MAX / 2);
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        if (station[i - 1][0] <= duration) {
            dp[i] = static_cast(station[i - 1][0]) / velocity + station[i - 1][1] + 1;
            continue;
        }
        for (int j = i - 1; j >= 1; j--) {
            if (dp[j] != INT_MAX / 2 && station[i - 1][0] - station[j - 1][0] <= duration) {
                dp[i] = min(dp[i], dp[j] +
                           static_cast(station[i - 1][0] - station[j - 1][0]) / velocity +
                            station[i - 1][1] + 1);
            }
        }
    }
    int minHour = INT_MAX / 2;
    for (int i = 1; i <= N; i++) {
        if (dp[i] != INT_MAX / 2 && station[i - 1][0] + duration >= D) {
            minHour = min(minHour, static_cast(dp[i]
                         + (D - station[i - 1][0]) / velocity));
        }
    }
    if (minHour != INT_MAX / 2) {
        printf("%d\n", minHour);
    } else {
        printf("%d\n", -1);
    }
    return 0;
}