目录

题目

思路

Code

题目

题目内容
某新能源公司有N个充电桩和M辆电动车需要充电。每辆车有一个预计到达时间和需要的充电时间。每辆车有预计到达时间AT、需要的充电时间CT、最大可等待时长WT(从到达后到开始充电的等待时间不能超过该值，否则车辆会离开，无法完成充电)。为了最大化充电桩利用率，需要设计调度算法，使得尽可能多的车辆能够按时完成充电。
规则:
·每个充电桩同一时间只能服务一辆车;
·车辆必须在其预计到达时间或之后开始充电;
一旦开始充电就不能中断;
车辆从到达后到开始充电的等待时间=开始充电时间一到达时间，该值必须<车辆的最大可等待时长，否则车辆无法充电;，目标是最小化未能按时完成充电的车辆数量(包括等待超时离开的车辆)。
·车辆到达场站后，若有充电桩空闲则立即充电，如果没有充电桩，则等待出现空闲充电桩后，先到的车辆先进行充电。

输入描述
输入包含一行数据, 格式:N,M.[AT1,CT1,WT1][AT2,CT2,WT2]....[ATM,CTM,WTM]
·整数N表示充电桩数量;
·整数M表示车辆数量;
M个一维数组[AT1,CT1,WT1]....[ATM,CTM,WTM]，表示每辆车的到达时间 AT、充电时间CT、最大可等待时长WT;
约束条件:
·1≤N≤100,1≤M≤1000,
1≤AT≤10000,1≤CT≤10000,0≤WT≤10000,
·不考虑最大可等待时长WT过长的合理性
输出描述
充电失败的车辆数量

样例1
输入
3 5
10,1,0 10,1,0 10,1,0 10,1,0 10,1,0
输出
2
说明
3个充电桩
5辆汽车
10 1 0//车辆1:到达10，充电1，最多等0(必须立即开始)
10 1 0//车辆2:到达10，充电1，最多等0(必须立即开始)
10 1 0//车辆3:到达10，充电1，最多等0(必须立即开始)
10 1 0//车辆4:到达10，充电1，最多等0(必须立即开始)
10 1 0//车辆5:到达10，充电1，最多等0(必须立即开始)车辆1时刻10到达，占用充电桩1进行充电，充电开始时间为10，充电时长为1，等待时间为0，充电结束时间为11，即充电桩1释放时刻为11，车辆1充电成功。
车辆2时刻10到达，充电桩2为空闲，充电开始时间为10，充电时长为1，充电结束时间为11，即充电桩2释放时刻为11，车辆2充电成功。
车辆3时刻10到达，充电桩3为空闲，充电开始时间为10，充电时长为1,充电结束时间为11，即充电桩3释放时刻为11,车辆3充电成功。
车辆4时刻10到达，充电桩123在10时刻均为占用状态，车辆4等待时间为0，必须立即充电，此时无充电桩空闲，因此车辆4充电失败。
车辆5时刻10到达，充电桩123在10时刻均为占用状态，车辆5等待时间为0，必须立即充电，此时无充电桩空闲，因此车辆5充电失败。
综上分析，车辆45充电失败，输出为2。

思路

事件驱动模拟 + FIFO 队列（优先级队列）

1. 预处理
将车辆按到达时间 AT 升序排序，生成两类事件：车辆到达事件、充电完成事件，推入最小堆按时间顺序处理。

2. 数据结构

• events：最小堆 (time, type, idx)，type=0 充电完成 / type=1 车辆到达
• pileFree：当前空闲充电桩数量
• waiting：FIFO 队列，存储等待车辆的索引

3. 核心逻辑（同一时刻 t 的处理顺序）
所有 time == t 的事件收集完毕后，按以下三步执行：

1. 充电完成 → 释放充电桩：pileFree += freedCount
2. 车辆到达 → 全部入队 waiting
3. 处理等待队列 → 循环：出队最早车辆，若 t - AT ≤ WT 则分配充电桩并推入完成事件，否则失败计数 +1（桩仍空闲，继续服务下一辆）

4. 正确性证明

• 同一时刻先处理「充电完成」再处理「到达并入队」，保证已等待的车辆优先于新到达车辆获得充电桩（FIFO 语义）。
• 当 wait > WT 时车辆离开，桩不分配，继续尝试队列中下一辆车，符合实际调度逻辑。
• 堆中后续新增的完成事件时间 t + CT 严格大于 t（CT ≥ 1），不会干扰当前时刻的处理。

5. 收尾
队列中残留车辆始终未等到空闲桩 → 全部计入失败。

6. 复杂度
时间 O(M log M)，空间 O(M)（M ≤ 1000，堆操作可忽略）。

Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
using namespace std;

struct Vehicle {
    int at, ct, wt;
};

struct Event {
    int time, type, idx; // type: 0=完成, 1=到达
    bool operator>(const Event& o) const {
        if (time != o.time) return time > o.time;
        return type > o.type;
    }
};

int solve(int N, int M, vector<Vehicle>& vehicles) {
    // 按到达时间排序
    sort(vehicles.begin(), vehicles.end(),
         [](const Vehicle& a, const Vehicle& b) { return a.at < b.at; });

    // 事件最小堆
    priority_queue<Event, vector<Event>, greater<Event>> pq;
    for (int i = 0; i < M; i++)
        pq.push({vehicles[i].at, 1, i});

    int pileFree = N;
    queue<int> waiting;
    int fail = 0;

    while (!pq.empty()) {
        int t = pq.top().time;

        // 收集 t 时刻所有事件
        int freed = 0;
        vector<int> arrivals;
        while (!pq.empty() && pq.top().time == t) {
            Event e = pq.top(); pq.pop();
            if (e.type == 0) freed++;
            else arrivals.push_back(e.idx);
        }

        pileFree += freed;
        for (int idx : arrivals) waiting.push(idx);

        // 用空闲桩服务等待队列
        while (pileFree > 0 && !waiting.empty()) {
            int idx = waiting.front(); waiting.pop();
            int wait = t - vehicles[idx].at;
            if (wait <= vehicles[idx].wt) {
                pileFree--;
                pq.push({t + vehicles[idx].ct, 0, -1});
            } else {
                fail++;
            }
        }
    }

    fail += waiting.size();
    return fail;
}

int main() {
    int N, M;
    cin >> N >> M;
    cin.ignore(); // consume newline

    string line;
    getline(cin, line);
    stringstream ss(line);
    string token;
    vector<Vehicle> vehicles;

    while (ss >> token) {
        stringstream ts(token);
        string part;
        vector<int> vals;
        while (getline(ts, part, ','))
            vals.push_back(stoi(part));
        vehicles.push_back({vals[0], vals[1], vals[2]});
    }

    cout << solve(N, M, vehicles) << endl;
    return 0;
}

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。