🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈
 
🍂个人博客首页： KJ.JK
 
💖系列专栏：华为OD机试真题(C++)

一、题目

🔸题目描述

张三要去外地出差，需要做核酸,需要在指定时间点前做完核酸，请帮他找到满足条件的核酸检测点。
 
 
● 给出一组核酸检测点的距离和每个核酸检测点当前的人数
 
● 给出张三要去做核酸的出发时间出发时间是10分钟的倍数，同时给出张三做核酸的最晚结束时间
 
● 题目中给出的距离是整数，单位是公里，时间1分钟为一基本单位
去找核酸点时，如下的限制：
 
1、去往核酸点的路上，每公里距离花费时间10分钟，费用是10元
2、核酸点每检测一个人的时间花费是1分钟
3、每个核酸点工作时间都是8点到20点中间不休息，核酸点准时工作,早到晚到都不检测
4、核酸检测结果可立刻知道
5、在张三去某个核酸点的路上花费的时间内，此核酸检测点的人数是动态变化的，变化规则是：
 
● 在非核酸检测时间内，没有人排队
 
● 28点-10点每分钟增加3人
 
● 12点-14点每分钟增加10人
 
要求将所有满足条件的核酸检测点按照优选规则排序列出: .
优选规则:
 
1.花费时间最少的核酸检测点排在前面。
2.花费时间一样花费费用最少的核酸检测点排在前面。
3.时间和费用一样，则ID值最小的排在前面

🔸输入输出

输入
H1 M1
H2 M2
N
ID1 D1 C1
ID2 D2 C2
IDn Dn Cn
H1:当前时间的小时数。
M1:当前时间的分钟数,
H2:指定完成核算时间的小时数。
M2:指定完成核算时间的分钟数。
N:所有核酸检测点个数。
ID1:核酸点的ID值。
D1:核酸检测点距离张三的距离。
C1:核酸检测点当前检测的人数。
 
输出
N
12 T2 M2
l3 T3 M3
N:满足要求的核酸检测点个数
12:选择后的核酸检测点ID
T2:做完核酸花费的总时间(分钟)
M3:去该核算点花费的费用

🔸样例1

输入
10 30
14 50
3
1 10 19
2 8 20
3 21 3输出
2
2 80 80
1 190 100

二、题目解析

张三在10:30出门，要在14:50之前做完核酸。
 
现在张三可选三个核酸检测点:
●检测点1:距离张三10公里， 10:30的时候有19个人排队
●检测点2:距离张三8公里，10:30的时候有20个人排队
●检测点3:距离张三21公里，10:30的时候有3个人排队
 
现在假设张三去检测点1
 
张三赶到检测点1，需要10 * 10= 100元，10 * 10=100分钟， 张三到达检测点时12:10.
 
在10:30~12:00期间不会有人加入，只会有人离开,每分钟离开1人，因此到12:00时，最多离开12 * 60 - (10* 60+30)= 90人，而10:30时
只有19人排队，因此到12:00时，检测点1只有0人排队。
 
然后12:00到12:10阶段，每分钟离开1人，增加10人，因此相当于每分钟净增9人,因此到12:10.即张三到达时，检测点共有: 10*9=
90人。
 
因此张三还需排90分钟，才能做完核酸。
 
因此张三到检测点1的代价是:路上100分钟，到达后等待90分钟，共需190分钟，花费100元。
 
同理，可得张三去其他检测点的代价。
 
然后，过滤掉花费时间超出限制的代价,剩下的按照花费时间、花费金额排序即可。
我们可以通过求区间交集的方式，来获取张三【出发时间，到达时间】和【8:00, 10:00】 以及【10:00, 12:00】，以及【12:00, 14:00】以及【14:00，20:00】的交集。
 
其中，
● 和 [ 8:00, 10:00 ]的交集，每分钟净增2人
● 和 [10:00, 12:00 ]的交集，每分钟净减1人
● 和 [12:00, 14:00 ]的交集，每分钟净增9人
● 和 [14:00， 20:00 ] 的交集，每分钟净减1人
 
请注意：
如果张三在8:00前就赶到了核酸监测点，但是8:00前是不给排队的，因此张三还要等待到8:00，因此张三花费的时间其实是:路上时间+
等待时间+排队时间

三、代码参考

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int getIntersection(vector<int>& timeRange1, vector<int>& timeRange2) {int start1 = timeRange1[0], end1 = timeRange1[1];int start2 = timeRange2[0], end2 = timeRange2[1];// 如果时间段1在时间段2之前，或者时间段1在时间段2之后，则没有交集if (start1 < start2) {if (start2 >= end1) return -1;else return min(end1, end2) - start2;}else if (start1 > start2) {if (start1 >= end2) return -1;else return min(end1, end2) - start1;}else {return min(end1, end2) - start1;}
}void getResult(int currentHour, int currentMinute, int targetHour, int targetMinute, vector<vector<int>>& nucleicAcidPoints) {// 将时间转换成分钟数int start = currentHour * 60 + currentMinute;int end = targetHour * 60 + targetMinute;// 计算每个核酸点的到达时间、花费时间、收费金额vector<vector<int>> result(nucleicAcidPoints.size());for (int i = 0; i < nucleicAcidPoints.size(); i++) {int id = nucleicAcidPoints[i][0];int distance = nucleicAcidPoints[i][1];int count = nucleicAcidPoints[i][2];int money = distance * 10; // 收费金额为距离*10int road = distance * 10; // 花在路上的时间为距离*10int arrived = start + road; // 到达核酸检测点的时间// 如果在8：00之前就赶到了，那么其实要等待到8:00才能排队，这里其实花费的时间应该包括等待的时间if (arrived < 8 * 60) {arrived = 8 * 60;road = arrived - start;}// 计算在不同时间段内排队的人数vector<int> timeRange1 = { start, arrived }; // 出发时间、到达时间vector<int> timeRange2 = { 8 * 60, 10 * 60 }; // 8:00-10:00int add1 = getIntersection(timeRange1, timeRange2); // 交集长度if (add1 != -1) {count += 2 * add1; // 每分钟净增2人}vector<int> timeRange3 = { 10 * 60, 12 * 60 }; // 10:00-12:00int min1 = getIntersection(timeRange1, timeRange3); // 交集长度if (min1 != -1) {count -= min1; // 每分钟净减1人count = max(0, count); // 注意至多减到0}vector<int> timeRange4 = { 12 * 60, 14 * 60 }; // 12:00-14:00int add2 = getIntersection(timeRange1, timeRange4); // 交集长度if (add2 != -1) {count += 9 * add2; // 每分钟净增9人}vector<int> timeRange5 = { 14 * 60, 20 * 60 }; // 14:00-20:00int min2 = getIntersection(timeRange1, timeRange5); // 交集长度if (min2 != -1) {count -= min2; // 每分钟净减1人count = max(0, count); // 注意至多减到0}result[i] = { id, count + road, money }; // 返回核酸点的ID、到达时间+花费时间、收费金额}// 过滤出规定结束时间end之前可达的核酸点result.erase(remove_if(result.begin(), result.end(), [&](vector<int>& arr) { return start + arr[1] > end; }), result.end());// 按照到达时间+花费时间、收费金额、ID的顺序排序sort(result.begin(), result.end(), [](vector<int>& a, vector<int>& b) { return a[1] != b[1] ? a[1] < b[1] : a[2] != b[2] ? a[2] < b[2] : a[0] < b[0]; });// 输出结果cout << result.size() << endl;for (vector<int>& arr : result) {cout << arr[0] << " " << arr[1] << " " << arr[2] << endl;}
}int main() {int currentHour, currentMinute, targetHour, targetMinute;cin >> currentHour >> currentMinute >> targetHour >> targetMinute;// 读取输入的核酸点信息int n;cin >> n;vector<vector<int>> nucleicAcidPoints(n, vector<int>(3));for (int i = 0; i < n; i++) {cin >> nucleicAcidPoints[i][0] >> nucleicAcidPoints[i][1] >> nucleicAcidPoints[i][2];}// 调用getResult方法计算结果getResult(currentHour, currentMinute, targetHour, targetMinute, nucleicAcidPoints);return 0;
}

作者：KJ.JK

文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习