C++ 优化列车调度方案 - 最少机车使用

这是一个经典的调度问题，可以使用贪心算法来解决。具体思路如下：

对于每个站点，将到达列车和出发列车按时间顺序排序。
初始化机车数量为0，当前时间为第一班列车的到达时间。
从A站开始，依次考虑每个列车的到达和出发时间，如果当前时间小于等于该列车的到达时间，则需要一个新的机车，且当前时间更新为该列车的到达时间加上整备作业时间。
如果当前时间大于该列车的到达时间，则可以考虑将前面的机车用于该列车的牵引，且当前时间更新为该列车的出发时间加上整备作业时间。
继续考虑下一个列车，直到所有列车都被考虑完毕。
输出所需要的机车数量和每个机车所牵引的列车数目。

下面是代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Train {
    int id;
    int time;
};

bool cmp(Train a, Train b) {
    return a.time < b.time;
}

int main() {
    // A站到达列车
    vector<Train> a_arrive = {{302, 1830}, {304, 2200}, {306, 80}, {308, 130}, {310, 280}, {312, 420}, {314, 600}, {316, 720}, {318, 870}, {320, 990}};
    // A站出发列车
    vector<Train> a_depart = {{301, 1100}, {303, 1280}, {305, 1410}, {307, 210}, {309, 320}, {311, 510}, {313, 750}, {315, 950}};
    // B站到达列车
    vector<Train> b_arrive = {{301, 230}, {303, 440}, {305, 570}, {307, 750}, {309, 890}, {311, 1080}, {313, 1350}, {315, 1850}};
    // B站出发列车
    vector<Train> b_depart = {{302, 540}, {304, 720}, {306, 860}, {308, 960}, {310, 1120}, {312, 1290}, {314, 1470}, {316, 1590}, {318, 1700}, {320, 1900}};
    // 机车整备作业时间
    int prep_time = 100;
    // 初始化机车数量和当前时间
    int num_train = 0;
    int curr_time = a_arrive[0].time;
    // 处理A站到达列车
    for (int i = 0; i < a_arrive.size(); i++) {
        if (curr_time <= a_arrive[i].time) {
            num_train++;
            curr_time = a_arrive[i].time + prep_time;
        } else {
            curr_time = max(curr_time, a_arrive[i].time + prep_time);
        }
    }
    // 处理A站出发列车
    for (int i = 0; i < a_depart.size(); i++) {
        if (curr_time <= a_depart[i].time) {
            num_train++;
            curr_time = a_depart[i].time + prep_time;
        } else {
            curr_time = max(curr_time, a_depart[i].time + prep_time);
        }
    }
    // 处理B站到达列车
    for (int i = 0; i < b_arrive.size(); i++) {
        if (curr_time <= b_arrive[i].time) {
            num_train++;
            curr_time = b_arrive[i].time + prep_time;
        } else {
            curr_time = max(curr_time, b_arrive[i].time + prep_time);
        }
    }
    // 处理B站出发列车
    for (int i = 0; i < b_depart.size(); i++) {
        if (curr_time <= b_depart[i].time) {
            num_train++;
            curr_time = b_depart[i].time + prep_time;
        } else {
            curr_time = max(curr_time, b_depart[i].time + prep_time);
        }
    }
    // 输出结果
    cout << '机车数量: ' << num_train << endl;
    cout << '每个机车牵引的列车数目:' << endl;
    // 对所有列车按时间排序
    vector<Train> all_trains = a_arrive;
    all_trains.insert(all_trains.end(), a_depart.begin(), a_depart.end());
    all_trains.insert(all_trains.end(), b_arrive.begin(), b_arrive.end());
    all_trains.insert(all_trains.end(), b_depart.begin(), b_depart.end());
    sort(all_trains.begin(), all_trains.end(), cmp);
    // 处理所有列车
    int curr_train = 1;
    for (int i = 0; i < all_trains.size(); i++) {
        if (i > 0 && all_trains[i].time != all_trains[i-1].time) {
            curr_train++;
        }
        cout << '机车' << curr_train << '牵引列车' << all_trains[i].id << endl;
    }
    return 0;
}

代码解释:

结构体定义: Train 结构体用于存储列车信息，包括列车编号 (id) 和到达/出发时间 (time)。
排序函数: cmp 函数用于对 Train 结构体按照时间排序。
数据初始化: 初始化到达和出发列车信息，以及机车整备时间。
贪心算法: 使用循环遍历所有列车，并根据当前时间和列车时间来判断是否需要新机车。
输出结果: 输出需要的机车数量和每个机车牵引的列车数目。

注意: 代码中的时间单位为分钟。

通过以上代码，我们可以得到最少机车数量和每个机车牵引的列车数目，从而实现列车调度优化。