标准解答

/**
 * 题目：拼车计划 (Car Pooling)
 * 知识点：差分数组 (Difference Array)
 * 时间复杂度：O(max_location)
 * 空间复杂度：O(max_location)
 */

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

using namespace std;

const int MAX_LOCATION = 1005; // 题目中车站最大编号为 1000
int diff[MAX_LOCATION];        // 全局差分数组，自动初始化为 0

int main() {
    // 1. IO 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, c;
    if (!(cin >> n >> c)) return 0;

    int max_stop = 0; // 记录最远的车站编号，减少后续遍历次数

    // 2. 读入订单并构建差分数组
    for (int i = 0; i < n; ++i) {
        int k, s, e;
        cin >> k >> s >> e;

        // 核心操作：
        // 在 s 站上车：人数 +k
        diff[s] += k;
        // 在 e 站下车：人数 -k (注意：区间是 [s, e-1]，e点已经没人了)
        diff[e] -= k;

        max_stop = max(max_stop, e);
    }

    // 3. 扫描差分数组，检查是否超载
    // current_load 相当于对 diff 数组求前缀和
    int current_load = 0;
    bool possible = true;

    for (int i = 0; i <= max_stop; ++i) {
        current_load += diff[i];

        // 检查当前时刻是否超载
        if (current_load > c) {
            possible = false;
            break; // 一旦发现超载，立即停止
        }
    }

    // 4. 输出结果
    if (possible) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

这是一个完整的 C++ 数据生成器，用于生成“拼车计划”题目的测试数据。

该生成器包含了一个标准的差分数组解法用于生成正确的 .out 文件，并设计了 10 个测试点，覆盖了从样例、边界情况（单人行程、全程覆盖、首尾相接）到最大规模压力测试的各种场景。

数据生成器代码 (generator.cpp)

您可以将以下代码保存为 generator.cpp，编译并运行。它将在当前目录下生成 1.in/1.out 到 10.in/10.out。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <ctime>
#include <algorithm>

using namespace std;

// 订单结构
struct Trip {
    int num_passengers;
    int start_loc;
    int end_loc;
};

// ==========================================
// 1. 辅助函数：计算完成所有订单所需的最大容量
// ==========================================
int get_required_capacity(const vector<Trip>& trips) {
    // 题目中车站最大编号为 1000
    int diff[1005] = {0};
    int max_loc = 0;

    for (const auto& t : trips) {
        diff[t.start_loc] += t.num_passengers;
        diff[t.end_loc] -= t.num_passengers; // 乘客在 end_loc 下车，不再占用空间
        max_loc = max(max_loc, t.end_loc);
    }

    int current_load = 0;
    int max_load = 0;
    for (int i = 0; i <= max_loc; ++i) {
        current_load += diff[i];
        max_load = max(max_load, current_load);
    }
    return max_load;
}

// ==========================================
// 2. 标准解法函数 (用于生成 .out 文件)
// ==========================================
string solve(int n, int c, const vector<Trip>& trips) {
    int required = get_required_capacity(trips);
    if (required <= c) return "Yes";
    else return "No";
}

// ==========================================
// 3. 随机数辅助工具
// ==========================================
mt19937 rng(time(nullptr));

// 生成 [min, max] 范围内的随机整数
int random_int(int min, int max) {
    if (min > max) return min;
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

// ==========================================
// 4. 测试点生成逻辑
// ==========================================
void generate_test_case(int id) {
    int N, C;
    vector<Trip> trips;
    string desc;

    switch (id) {
        case 1: // 样例 1 (超载)
            N = 2; C = 4;
            trips = {{2, 1, 5}, {3, 3, 7}};
            desc = "Sample 1 (No)";
            break;
        case 2: // 样例 2 (可行)
            N = 2; C = 5;
            trips = {{2, 1, 5}, {3, 3, 7}};
            desc = "Sample 2 (Yes)";
            break;
        case 3: // 极小边界：单人单程，刚好坐满
            N = 1; C = 10;
            trips = {{10, 0, 100}};
            desc = "Single Trip Exact Capacity";
            break;
        case 4: // 极小边界：单人单程，超载
            N = 1; C = 9;
            trips = {{10, 0, 100}};
            desc = "Single Trip Over Capacity";
            break;
        case 5: // 全程覆盖边界：从 0 到 1000
            N = 20; 
            for(int i=0; i<N; ++i) trips.push_back({5, 0, 1000});
            C = 100; // 刚好 20*5 = 100
            desc = "Full Range Overlap";
            break;
        case 6: // "接力"测试：下车点等于上车点
            // 测试逻辑是否正确处理了 "end点乘客已下车"
            // 行程: [0, 5], [5, 10], [10, 15]... 
            // 在点 5，第一批下车，第二批上车，负载不应翻倍
            N = 50; C = 10;
            for(int i=0; i<N; ++i) {
                trips.push_back({10, i*10, (i+1)*10});
            }
            desc = "Chain Connections (Drop off logic)";
            break;
        case 7: // 随机数据：构造 Yes 的情况
            N = 100;
            for(int i=0; i<N; ++i) {
                int s = random_int(0, 900);
                int e = random_int(s+1, 1000);
                int k = random_int(1, 50);
                trips.push_back({k, s, e});
            }
            // 计算最大需求，设定容量刚好满足
            C = get_required_capacity(trips); 
            desc = "Random Valid (Capacity = Max Load)";
            break;
        case 8: // 随机数据：构造 No 的情况
            N = 100;
            for(int i=0; i<N; ++i) {
                int s = random_int(0, 900);
                int e = random_int(s+1, 1000);
                int k = random_int(1, 50);
                trips.push_back({k, s, e});
            }
            // 设定容量比需求少 1
            C = get_required_capacity(trips) - 1;
            desc = "Random Invalid (Capacity < Max Load)";
            break;
        case 9: // 大规模数据 N=1000 (Valid)
            N = 1000;
            for(int i=0; i<N; ++i) {
                int s = random_int(0, 950);
                int e = random_int(s+1, 1000);
                int k = random_int(1, 100);
                trips.push_back({k, s, e});
            }
            C = get_required_capacity(trips);
            desc = "Max N Valid";
            break;
        case 10: // 大规模数据 N=1000 (Invalid)
            N = 1000;
            for(int i=0; i<N; ++i) {
                int s = random_int(0, 950);
                int e = random_int(s+1, 1000);
                int k = random_int(1, 100);
                trips.push_back({k, s, e});
            }
            C = get_required_capacity(trips) / 2; // 容量减半，必然超载
            desc = "Max N Invalid";
            break;
    }

    // --- 写入 .in 文件 ---
    string in_filename = to_string(id) + ".in";
    ofstream fin(in_filename);
    fin << N << " " << C << "\n";
    for (const auto& t : trips) {
        fin << t.num_passengers << " " << t.start_loc << " " << t.end_loc << "\n";
    }
    fin.close();

    // --- 计算答案并写入 .out 文件 ---
    string result = solve(N, C, trips);
    string out_filename = to_string(id) + ".out";
    ofstream fout(out_filename);
    fout << result << "\n";
    fout.close();

    cout << "Generated Case " << id << ": " << desc << " (N=" << N << ", C=" << C << ")" << endl;
}

int main() {
    // 加速 I/O
    ios::sync_with_stdio(false);
    
    for (int i = 1; i <= 10; ++i) {
        generate_test_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

测试点详细设计说明

1. Case 1 (Sample No): 题目自带的超载样例。
2. Case 2 (Sample Yes): 题目自带的可行样例。
3. Case 3 (Single Trip Valid): $N=1$，且人数等于容量。测试边界 $CurrentLoad == Capacity$ 是否判定为可行。
4. Case 4 (Single Trip Invalid): $N=1$，且人数大于容量。测试最简单的超载。
5. Case 5 (Full Range): 所有行程都从 0 到 1000，且叠加后刚好等于容量。测试最长区间的叠加处理。
6. Case 6 (Chain Connections): “接力”测试。行程如 [0,5], [5,10], [10,15]。在站点 5，一批人下车，一批人上车。此测试点用于验证程序是否正确处理了“下车点不占空间”的逻辑（即 diff[end] -= k 或者是区间 [start, end)）。如果处理成了 [start, end]，此测试点会误判为超载。
7. Case 7 (Random Valid): 随机生成行程，并计算出最大负载，将容量设为该负载，强制生成 Yes 的测试点。
8. Case 8 (Random Invalid): 随机生成行程，将容量设为最大负载减 1，强制生成 No 的测试点。
9. Case 9 (Max N Valid): $N=1000$ 的压力测试，结果为 Yes。
10. Case 10 (Max N Invalid): $N=1000$ 的压力测试，容量设得很小，结果为 No。

如何使用

1. 保存：将代码保存为 generator.cpp。
2. 编译：g++ generator.cpp -o generator -O2
3. 运行：./generator
4. 结果：当前文件夹下会生成 1.in, 1.out ... 10.in, 10.out。可以直接上传到 OJ 后台。