优先队列保存窗口时间，每次选出最小时间处理

讲解算法思路代码部分pat运行结果复杂度分析

讲解

设置一个将题干hh:mm:ss时间转化为秒为单位的时间的函数利用一个优先队列（这里是一个小根堆，每次top为时间最小的元素）保存每个窗口的当前时间将每个人的个人信息用struct保存，包括到达时间和处理时间将每个人以到达时间排序（由小到大），先到的先处理开始模拟银行工作： 1）取出当前时间time_win（就是该窗口上一次处理的结束时间，初始化为8*3600）最小的银行窗口，接受最早到达的人的申请 2）修改当前窗口的结束时间为time_win + 处理人的执行时间process（这就是该窗口下一次可以接受申请的时间） 3）将该窗口信息重新入队，然后循环这三步，代码中有详细注释

算法思路

思路源自于模拟正常银行工作流程，哪个窗口先空闲哪个窗口工作，符合优先队列的性质，然后先到的人先安排，所以要排序

代码部分

代码中包含了测试输出语句，方便读者copy后去测试pat例子，这里已经注释掉了，可以直接在pat提交

#include <iostream> #include <cstdlib> #include <algorithm> #include <ostream> #include <queue> using namespace std; /** 保存8:00 和 17:00 的秒进制时间 **/ const int Start = 8*3600; const int End = 17*3600; /** 建立一个结构体，保存每个人的到达时间和执行时间 **/ struct node{ int arr_time; int pro_time; bool operator < (const node& n1)const{ return this->arr_time < n1.arr_time; } // friend ostream& operator << (ostream& os,const node& n){ // os<<n.arr_time<<" "<<n.pro_time<<endl; // return os; // } }; vector<node> people; /** 时间转化函数 **/ int time_int(string& s){ string hh = s.substr(0,2),mm = s.substr(3,2),ss = s.substr(6,2); int hi = atoi(hh.c_str()),mi= atoi(mm.c_str()),si = atoi(ss.c_str()); return hi*3600 + mi*60 + si; //转换成秒保存 } int main() { int N,K; cin>>N>>K; /** 创建一个容量为K的小根堆,表示k个窗口 **/ priority_queue<int,vector<int>,greater<int>> pq; for(int i=0;i<K;i++) pq.push(Start); for(int i=0;i<N;i++){ string arrive; // 到达时间 int process; // 办理时间 cin>>arrive>>process; people.push_back({time_int(arrive),process*60}); } sort(people.begin(),people.end()); // cout<<"start = "<<Start<<endl; // cout<<"End = "<<End<<endl; // for(int i=0;i<people.size();i++){ // cout<<people[i]; // } /** 处理每一个人 **/ double ans = 0; int realN = 0; for(int i=0;i<N;i++){ node f = people[i]; // 获取最先到达的一个人 if(f.arr_time > End) continue; // 超时到达不处理 realN++; // cout<<"i = "<<i<<endl; int temp_win = pq.top(); // 获取第一个空闲的窗口 // cout<<"第一个空闲窗口时间为："<<temp_win<<endl; pq.pop(); int arr_time = f.arr_time; if(arr_time <= temp_win){ // 到达时没有空闲窗口，需要等待 ans += temp_win-arr_time; // 累计等待时间 temp_win += f.pro_time; // 修改当前窗口的下一次空闲时刻 pq.push(temp_win); }else{ // 到达时有空闲窗口，无需等待直接工作 temp_win = arr_time + f.pro_time; pq.push(temp_win); } } printf("%.1f",ans/realN/60); return 0; }

pat运行结果

复杂度分析

时间复杂度：对N个人时间排序的时间为O（NlogN），然后需要对每个人处理一次，还有入队出队的处理，处理时间为O（N），队列调整时间为O（log（K）），整体时间复杂度为O（max(Nlog(N),log(K))）;空间复杂度：优先队列复杂度为O（K），结构体信息复杂度为O（N），整体复杂度为O（K+N）；

感谢大家观看！欢迎评论区批评指正。