请用简单的c++语言解决以下问题假设银行有K个窗口提供服务,窗口前设一条黄线,所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时,下一位顾客即去该窗口处理事务。当有多个窗口可选择时,假设顾客总是选择编号最小的窗口。 本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间,并且统计每个窗口服务了多少名顾客。 输入描述: 输入第1行给出正整数N(≤1000),为顾客总人数;随后N行,每行给出一位顾客的到达时间T和事务处理时间P,并且假设输入数据已经按到达时间先后排好了顺序;最后一行给出正整数K(≤10),为开设的营业窗口数。输出描述: 在第一行中输出平均等待时间、最长等待时间、最后完成时间,之间用一个空格分隔。 在第二行中按编号递增顺序输出每个窗口服务了多少名顾客,数字之间用一个空格分隔。
时间: 2024-03-12 21:44:13 浏览: 68
基于队列的银行窗口设置模拟
以下是C++代码实现:
```c++
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct Customer {
int id; // 顾客编号
int arrive_time; // 到达时间
int process_time; // 事务处理时间
int start_time; // 开始服务时间
int finish_time; // 完成服务时间
int wait_time; // 等待时间
bool operator < (const Customer& c) const { // 重载<运算符
return arrive_time > c.arrive_time; // 按到达时间从小到大排序
}
};
struct Window {
int id; // 窗口编号
int finish_time; // 完成服务时间
int count; // 服务人数
bool operator < (const Window& w) const { // 重载<运算符
if(finish_time == w.finish_time) { // 如果窗口完成服务时间相等
return id > w.id; // 按窗口编号从小到大排序
}
return finish_time > w.finish_time; // 按完成服务时间从小到大排序
}
};
int main() {
int n, k;
cin >> n;
vector<Customer> customers(n);
for(int i = 0; i < n; i++) {
customers[i].id = i + 1;
cin >> customers[i].arrive_time >> customers[i].process_time;
}
cin >> k;
vector<Window> windows(k);
for(int i = 0; i < k; i++) {
windows[i].id = i + 1;
windows[i].finish_time = 0;
windows[i].count = 0;
}
priority_queue<Customer> q; // 顾客队列
for(int i = 0; i < n; i++) {
if(q.empty()) { // 如果顾客队列为空,直接将顾客加入队列
q.push(customers[i]);
} else { // 否则,找到最早完成服务的窗口
int j = 0;
for(int k = 1; k < windows.size(); k++) {
if(windows[k].finish_time < windows[j].finish_time) {
j = k;
}
}
if(customers[i].arrive_time >= windows[j].finish_time) { // 如果该顾客可以立刻服务
customers[i].start_time = customers[i].arrive_time;
customers[i].finish_time = customers[i].start_time + customers[i].process_time;
customers[i].wait_time = 0;
windows[j].finish_time = customers[i].finish_time;
windows[j].count++;
} else { // 否则,将顾客加入队列等待服务
q.push(customers[i]);
}
}
while(!q.empty()) { // 处理等待顾客
bool flag = false; // 标志是否有窗口可以服务等待顾客
for(int j = 0; j < windows.size(); j++) {
if(windows[j].finish_time <= q.top().arrive_time) { // 如果该窗口完成服务时间早于等待顾客到达时间
flag = true;
Customer c = q.top();
c.start_time = q.top().arrive_time;
c.finish_time = c.start_time + c.process_time;
c.wait_time = c.start_time - c.arrive_time;
windows[j].finish_time = c.finish_time;
windows[j].count++;
q.pop();
break;
}
}
if(!flag) { // 如果没有窗口可以服务等待顾客,跳出循环
break;
}
}
}
double avg_wait_time = 0.0;
int max_wait_time = 0;
int last_finish_time = 0;
for(int i = 0; i < n; i++) {
avg_wait_time += customers[i].wait_time;
max_wait_time = max(max_wait_time, customers[i].wait_time);
last_finish_time = max(last_finish_time, customers[i].finish_time);
}
avg_wait_time /= n;
printf("%.1f %d %d\n", avg_wait_time, max_wait_time, last_finish_time);
for(int i = 0; i < k; i++) {
cout << windows[i].count;
if(i < k - 1) {
cout << " ";
}
}
cout << endl;
return 0;
}
```
注意事项:
1. 顾客和窗口都按编号从小到大排序;
2. priority_queue用于维护等待服务的顾客队列,其中重载<运算符;
3. 每个循环中都需要处理等待服务的顾客,直到没有窗口可以服务等待顾客为止;
4. 输出结果时,注意使用printf输出小数,并且保留一位小数。
阅读全文