洛谷B4156 [厦门小学生 C++ 2023] 太空旅行

Question

洛谷B4156 [厦门小学生 C++ 2023] 太空旅行
题目描述
在未来，太空旅行已经是一件稀松平常的事，星际部又宣称即将开通一条火星至天王星的航线。

所有的星际飞船必须先经过航线 1（地球 → 火星），再经过航线 X（火星 → 天王星）才能顺利抵达天王星。

为了避免星际飞船发生碰撞，每条航线只能有一架飞船正在行驶。已知星际飞船从地球到火星需要 U(i) 时间，火星到天王星需要 V(i) 时间。飞船们可能会滞留在火星，它们必须等待航线状态为空才能起飞。飞船到达火星和离开火星的顺序可能会不一致。

请计算从地球出发的 N 架星际飞船，全部抵达天王星，需要花费的最短时间。

输入格式
第 1 行：一个整数 N，表示星际飞船的数量。

第 2 到 N+1 行：第 i+1 行包含两个空格隔开的整数：U(i) 和 V(i)。

输出格式
输出 1 行，一个单独的整数，表示所有飞船抵达天王星需要的最短时间。

输入输出样例
输入
3
6 4
8 1
2 3
输出
17

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

为了求解这个问题，我们需要有效地安排飞船在这两个航线上的飞行时间，确保每架飞船只有在前一架飞船完成后才能出发。这是一个调度问题，我们可以采用贪心算法的策略来实现最小化总时间。

解题思路

1. 数据结构：
   • 使用一个数组存储每架飞船的从地球到火星所需的时间 (U[i]) 和从火星到天王星所需的时间 (V[i])。
2. 飞船的排序：
   • 为了优化总时间，我们可以首先对飞船进行排序。根据每架飞船的火星到天王星的时间 (V[i])，我们希望更快的火星到天王星的时间尽早的被安排，以减少整体的等待时间。
3. 时间计算：
   • 使用两个变量来记录当前时间：
     • current_time 记录当前的总时间。
     • next_departure_time 记录下一个可以从火星离开的时间。
   • 遍历所有飞船，依次计算每架飞船到达天王星的时间。

算法步骤

1. 读取输入，存储飞船的到达和离开的时间。
2. 对飞船按照 V[i] 从小到大排序。
3. 遍历排序后的飞船，更新当前时间和下一个可以起飞的时间，计算所有飞船到达天王星的总时间。

代码实现

下面是 C++ 的实现代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Spaceship {
    int U; // Earth to Mars time
    int V; // Mars to Uranus time
};
// 升序排序的比较函数
bool compare(const Spaceship &a, const Spaceship &b) {
    return a.V < b.V; // 根据 V 值排序
}
int main() {
    int N;
    cin >> N;
    vector<Spaceship> spaceships(N);
    for (int i = 0; i < N; i++) {
        cin >> spaceships[i].U >> spaceships[i].V;
    }
    // 按 V 升序排序
    sort(spaceships.begin(), spaceships.end(), compare);
    int current_time = 0;        // 当前时间
    int next_departure_time = 0; // 下一个可以出发的时间
    int total_time = 0;          // 所有飞船到达时间的总和
    for (const auto &ship : spaceships) {
        // 更新当前时间，飞船从地球到达火星
        current_time += ship.U;
        // 记录在火星的等待时间，需等待前一架飞船出发
        next_departure_time = max(next_departure_time, current_time);
        // 增加从火星到天王星的飞行时间
        next_departure_time += ship.V;
        // 更新时间总和
        total_time = next_departure_time; // 更新总时间到当前飞船的到达时间
    }
    cout << total_time << endl; // 输出所有飞船到达天王星的最短时间
    return 0;
}

说明

• 在以上代码中，使用了一个 Spaceship 结构体来存储每架飞船的时间。
• compare 函数用于排序操作。
• 主函数中，通过顺序执行飞船，计算每架飞船到达天王星的时间，最终输出所需的最短时间。

时间复杂度

• 排序的时间复杂度为 (O(N \log N))，遍历飞船的时间复杂度为 (O(N))，因此整体时间复杂度为 (O(N \log N))。由于给定的限制条件合理，这种复杂度是可以接受的。