P14384.优化充电桩调度算法(200分)
题目内容
某新能源公司有 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 到达，充电桩 1 2 3 在 10 时刻均为占用状态，车辆 4 等待时间为 0，必须立即充电，此时无充电桩空闲，因此车辆 4 充电失败。
车辆 5 时刻 10 到达，充电桩 1 2 3 在 10 时刻均为占用状态，车辆 5 等待时间为 0，必须立即充电，此时无充电桩空闲，因此车辆 5 充电失败。
综上分析，车辆 4 5 充电失败，输出为 2。
样例2
输入
2,4,[[1,10,0],[2,2,1],[3,1,0],[4,1,0]]
输出
1
说明
- 2 个充电桩
- 4 辆汽车
- 1 10 0 // 车辆 1：到达 1，充电 10，最多等 0（必须立即开始）
- 2 2 1 // 车辆 2：到达 2，充电 2，最多等 1（开始充电时间 ≤3）
- 3 1 0 // 车辆 3：到达 3，充电 1，最多等 0（必须立即开始）
- 4 1 0 // 车辆 4：到达 4，充电 1，最多等 0（必须立即开始）
车辆 1 先到占用充电桩 1 进行充电，充电开始时间为 1，充电时长为 10，充电结束时间为 11，即充电桩 1 释放时刻为 11，车辆 1 充电成功。
车辆 2 时刻 2 到达，充电桩 2 为空闲，充电开始时间为 2，充电时长为 2，充电结束时间为 4，即充电桩 2 释放时刻为 4，车辆 2 充电成功。
车辆 3 时刻 3 到达，3 时刻没有充电桩空闲，可以等待时间为 0，即 3 时刻必须进行充电，但是 3 时刻充电桩 1 充电桩 2 都还没有释放，车辆 3 充电失败。
车辆 4 时刻 4 到达，4 时刻充电桩 2 已经释放，车辆 4 可以正常充电，车辆 4 充电成功。
综上分析，只有车辆 3 充电失败，输出为 1。
