南山网站设计电话,欧美网站模版,用网站免费模板做网站要会什么,网站建设多少钱 知乎题目 题目大意
银行有k个窗口#xff0c;每个窗口只能服务1个人。如果3个窗口已满#xff0c;就需要等待。给出n个人到达银行的时间和服务时间#xff0c;要求计算每个人的平均等待时间。如果某个人的到达时间超过17:00:00#xff0c;则不被服务#xff0c;等待时间也不计…题目 题目大意
银行有k个窗口每个窗口只能服务1个人。如果3个窗口已满就需要等待。给出n个人到达银行的时间和服务时间要求计算每个人的平均等待时间。如果某个人的到达时间超过17:00:00则不被服务等待时间也不计算在内。如果某个人早于8:00:00到达那该人要至少等到8:00:00才能被服务。
思路
银行排队问题根据题意模拟和1014相似。首先考虑怎么处理字符串形式的时间这里我将小时分钟秒都计算出来到达时间用秒来表示。一个人有到达时间服务时间还要计算等待时间因此我用结构体来表示数据结构就用了一个结构体数组。因为要考虑先后顺序所以肯定要排序。
排序之后先考虑一般情况一个人的等待时间 窗口的最小结束服务时间 - 到达时间只有前面的某个窗口结束服务这个人才能开始服务。再考虑这个人的到达时间晚于窗口结束服务时间的情况也就是说他到银行的时候就已经有空位了。那么他的等待时间 0结束服务时间 到达时间 服务时间。因此需要一个window数组来记录每个窗口的结束服务时间也就是可以开始服务下一个人的时间。window数组初始化为8点也即每个窗口开始服务下一个人的时间是8点。
代码
#include iostream
#include vector
#include algorithm
#include climits
using namespace std;struct man{int begin; // 开始时间单位秒int time; // 服务时间单位秒int wait; // 等待时间单位秒
};bool cmp(man x, man y){return x.begin y.begin;
}int main(){int n, k;cin n k;vectorman v;vectorint window(k, 8 * 3600); // 记录每个窗口服务结束的时间for (int i 0; i n; i){string s0;int begin, time, wait 0;cin s0 time;if (s0 17:00:00){int h (s0[0] - 0) * 10 (s0[1] - 0);int m (s0[3] - 0) * 10 (s0[4] - 0);int s (s0[6] - 0) * 10 (s0[7] - 0);begin h * 3600 m * 60 s;v.push_back({begin, time * 60, wait});}}sort(v.begin(), v.end(), cmp);for (int i 0; i (int)v.size(); i){int mini 0, mint INT_MAX;for (int j 0; j k; j){if (mint window[j]){mint window[j];mini j;}} // 最小结束时间v[i].wait max(0, window[mini] - v[i].begin); // 考虑顾客到达时间在结束时间之后window[mini] max(window[mini], v[i].begin) v[i].time; // 考虑顾客到达时间在结束时间之后}double res 0.0;for (int i 0; i (int)v.size(); i){res v[i].wait;}res / (int)v.size() * 60.0;printf(%.1lf\n, res);return 0;
}
