微商城网站建设策划,二手交易网站开发方式,上海网站商城建设公司,粉末涂料做网站有用吗链接#xff1a;
1017 Queueing at Bank - PAT (Advanced Level) Practice (pintia.cn) 题目大意#xff1a;
有n个客户#xff0c;k个窗口。已知每个客户的到达时间和需要的时长#xff0c;如果有窗口就依次过去#xff0c;如果没有窗口就在黄线外等候#xff08;黄线…链接
1017 Queueing at Bank - PAT (Advanced Level) Practice (pintia.cn) 题目大意
有n个客户k个窗口。已知每个客户的到达时间和需要的时长如果有窗口就依次过去如果没有窗口就在黄线外等候黄线外只有一个队伍先来先服务求客户的平均等待时长
有 N 位顾客每位顾客有一个到达时间和处理时间。银行营业时间为 08:00:00 到 17:00:00顾客到达时间早于 08:00:00 需要等到银行开门晚于 17:00:01 的顾客不会被服务。需要计算的是所有顾客的平均等待时间等待时间是从顾客到达时算起直到他被某个窗口接待开始为止。顾客在窗口处理时长不能超过1小时。
处理逻辑
1. 输入数据与时间转换
首先代码从输入中读取客户的到达时间和服务时间并将这些信息保存为一个结构体数组 p[]。客户的到达时间come会被转换为秒数以便更方便地处理时间比较和计算。服务时间t是以分钟为单位的会转换为秒数。
2. 排序顾客
在所有输入数据处理完之后代码对有效的顾客按照到达时间进行排序。这样做的目的是确保顾客按照先到先服务的顺序进行处理。
3. 初始化窗口的空闲时间
银行有 k 个窗口初始时所有窗口都从 08:00:00 开始可以提供服务这个时间被转换为秒数 28800 秒。使用一个小顶堆priority_queue来存储每个窗口的空闲时间即每个窗口何时会变得空闲以便下一个顾客可以开始服务。
4. 处理每位顾客的等待时间
对于每一位顾客代码通过比较顾客到达时间与最早空闲的窗口时间来决定顾客是否需要等待。如果窗口空闲时间早于或等于顾客到达时间顾客可以直接服务否则顾客需要等待等待时间是窗口的空闲时间减去顾客到达时间。
无论顾客是否等待窗口的空闲时间都会更新为顾客服务结束后的时间即 max(pq.top(), p[i].come) p[i].t表示窗口在顾客服务结束后变得空闲。
5. 计算平均等待时间
最后代码计算所有顾客的总等待时间并输出平均等待时间单位是分钟保留 1 位小数。如果没有有效顾客则输出 0.0。
代码
#include bits/stdc.h
using namespace std;
const int N 1e4 10;typedef struct{int come, t; // come: 顾客到达时间秒t: 处理时间秒
} node;int cnt;
node p[N]; // 存储有效的顾客信息bool cmp(node a, node b) {return a.come b.come; // 按到达时间升序排序
}priority_queueint, vectorint, greaterint pq; // 小顶堆表示窗口的空闲时间int main() {int n, k;scanf(%d%d, n, k);for (int i 0; i n; i) {int hh, mm, ss, tt;scanf(%d:%d:%d %d, hh, mm, ss, tt);int t hh * 3600 mm * 60 ss; // 将时间转换为秒if (t 61200) continue; // 过滤掉 17:00:01 之后的顾客p[cnt].come t; // 存储顾客的到达时间p[cnt].t tt * 60; // 处理时间分钟转换为秒cnt;}// 对有效顾客按到达时间排序sort(p, p cnt, cmp);int wait 0; // 总等待时间for (int i 0; i k; i) pq.push(28800); // 所有窗口初始为空闲从 08:00:00 开始for (int i 0; i cnt; i) {if (pq.top() p[i].come) { // 如果窗口的最早空闲时间大于顾客到达时间wait pq.top() - p[i].come; // 顾客需要等待}// 更新窗口的空闲时间pq.push(max(pq.top(), p[i].come) p[i].t); // 顾客服务结束后的时间入堆pq.pop(); // 弹出已经处理完的窗口}// 输出平均等待时间单位为分钟保留 1 位小数if (cnt 0) {printf(0.0\n);} else {printf(%.1lf\n, (double)wait / 60.0 / (double)cnt);}return 0;
}
