目录
题目
思路
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的事件收集完毕后，按以下三步执行：
- 充电完成→ 释放充电桩：
pileFree += freedCount- 车辆到达→ 全部入队
waiting- 处理等待队列→ 循环：出队最早车辆，若
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。让他帮助你查询原因。
