问题分析

本题的核心是要找出汉森船长驾驶小驳船从汉堡到库克斯港的最优出发时间 $t$。需要满足两个条件：一是在 $t$时刻出发能保证在给定的截止时间 $d$之前到达库克斯港；二是在满足第一个条件的前提下，航行时间最短。若有多个满足条件的出发时间，则选择最晚的那个。 已知汉堡和库克斯港之间的距离为 $dtotal=100$千米，船在静水中的速度为 $vship=10$千米 / 小时。水流速度 $vdrift$会随时间变化，且变化信息由输入的数据集给出，船的实际速度 $vactual=vship+vdrift$。 ##解题思路 读取输入：读取测试用例的数量，对于每个测试用例，读取最晚到达时间 $d$和水流数据的数量，再依次读取每个水流数据（起始分钟 $m$和水流速度$s$）。 模拟航行：从最晚出发时间（即截止时间 $d$往前推）开始，逐步减小出发时间，模拟每次出发后的航行过程，计算到达时间。航行过程中根据不同时间段的水流速度计算实际速度，累加每个时间段行驶的距离，直到行驶完 100千米。筛选最优出发时间：在模拟过程中，记录满足在截止时间 $d$之前到达且航行时间最短的最晚出发时间。

cpp

#include #include

using namespace std;

// 水流数据结构体 struct DriftData { int minute; int speed; };

// 计算从出发时间开始的到达时间 int calculateArrivalTime(int departureTime, const vector& driftData) { double distance = 0; int currentTime = departureTime; int driftIndex = 0;

while (distance < 100) {
    // 找到当前时间对应的水流速度
    while (driftIndex < driftData.size() - 1 && currentTime >= driftData[driftIndex + 1].minute) {
        driftIndex++;
    }
    int driftSpeed = driftData[driftIndex].speed;
    double actualSpeed = 10 + driftSpeed;  // 实际速度
    // 计算下一分钟行驶的距离
    double distanceThisMinute = actualSpeed / 60.0;
    distance += distanceThisMinute;
    currentTime++;
}
return currentTime;

}

int main() { int scenarios; cin >> scenarios;

while (scenarios--) {
    int deadline;
    cin >> deadline;

    int dataCount;
    cin >> dataCount;

    vector<DriftData> driftData(dataCount);
    for (int i = 0; i < dataCount; ++i) {
        cin >> driftData[i].minute >> driftData[i].speed;
    }

    int optimalDeparture = 0;
    int minTravelTime = 100000;  // 初始化为一个较大值

    // 从截止时间往前推，尝试不同的出发时间
    for (int departure = deadline; departure >= 0; --departure) {
        int arrival = calculateArrivalTime(departure, driftData);
        if (arrival < deadline) {
            int travelTime = arrival - departure;
            if (travelTime <= minTravelTime) {
                minTravelTime = travelTime;
                optimalDeparture = departure;
            }
        }
    }

    cout << optimalDeparture << endl;
}

return 0;

}