# 7-4 single queue multi window plus VIP service for bank queuing problem

Suppose the bank has K windows to provide services, a yellow line is set in front of the window, and all customers form a long line behind the yellow line according to the arrival time. When a window is free, the next customer goes to the window to deal with affairs. When there are multiple windows to choose from, it is assumed that the customer always selects the window with the lowest number.

Some banks will provide VIP customers with various preferential services, such as opening a VIP window. In order to maximize the use of resources, the service mechanism of VIP window is defined as: when there are no VIP customers in the queue, the window serves ordinary customers; When the window is idle and there are VIP customers waiting in the queue, the VIP customers in the front row enjoy the service of the window. At the same time, when it's a VIP customer's turn to list, if the VIP window is not empty, the customer can choose a free ordinary window; Otherwise, be sure to select the VIP window.

This question requires to output the average waiting time, the longest waiting time and the final completion time of N customers waiting for service, and count how many customers are served in each window.

### Input format:

Enter line 1 to give a positive integer N (≤ 1000), which is the total number of customers; Then N lines, each line gives a customer's arrival time T, transaction processing time P and whether VIP flag (1 is VIP, 0 is not), and it is assumed that the input data has been arranged in order according to the arrival time; The last line gives the positive integer k (≤ 10) - the number of business windows opened and the number of VIP windows (from 0 to K − 1). It is assumed that the maximum time for each customer transaction to be processed is 60 minutes.

### Output format:

The waiting time between the first line and the last decimal place (the maximum waiting time after the output is separated by 1 space) and the average waiting time between the first line and the last decimal place.

In the second line, the number of customers served by each window is output in ascending order. The numbers are separated by a space, and there can be no extra space at the end of the line.

```10
0 20 0
0 20 0
1 68 1
1 12 1
2 15 0
2 10 0
3 15 1
10 12 1
30 15 0
62 5 1
3 1
```

### Output example:

```15.1 35 67
4 5 1
```

Topic idea:

Simulate the team with variable array, and simulate the window with variable array or ordinary array. Each time as long as the user meets the conditions, the time spent by the user in handling the business is added to the array of the simulation window, and each while loop makes now_time + 1, the total time spent in each window is - 1. This problem can be solved as long as VIP users give priority to judgment and the rest ordinary users judge later.

AC Code:

```#include <stdio.h>
#include <vector>

using namespace std;

struct user {
int GetTime;  // Arrival time of each user
int SpendTime;  // Time spent per user
int VIP;  // 1 is VIP, 0 is not;
};

int main() {
int n, n2, vip, now_time = 0;  // Define variables, n is the total number of customers and n2 is the number of business windows opened
vector <user> team;  // Use vector to represent the team
vector <int> win;  // You don't have to use vector. Ordinary arrays can also represent each window
int win_count[11] = {0};  // Count the usage times of each window
scanf("%d", &n);
for (int i = 0; i < n; i++) {
user PP;
scanf("%d%d%d", &PP.GetTime, &PP.SpendTime, &PP.VIP);
if (PP.SpendTime > 60) PP.SpendTime = 60;  // According to the meaning of the question, more than 60 minutes shall be counted as 60 minutes
team.push_back(PP);
}
scanf("%d%d", &n2, &vip);
for (int i = 0; i < n2; i++) {
win.push_back(0);  // The initial setting is 0
}
int long_time = 0;  // Maximum time
int avg_time = 0;  // average time
while (1) {
if (win[vip] == 0) {
// vip window is empty
for (int i = 0; i < (int)team.size(); i++) {
// Traverse the team to see if there are VIP users
if (now_time >= team[i].GetTime) {
// Check whether VIP users are in the team
if (team[i].VIP == 1) {
// VIP users
win[vip] += team[i].SpendTime;  // VIP window overtime
win_count[vip]++;  // Statistical times
avg_time += (now_time - team[i].GetTime);  // Statistical average time
if (now_time - team[i].GetTime > long_time) long_time = now_time - team[i].GetTime;  // Maximum waiting time for update
team.erase(team.begin() + i);  // Remove the user from the queue
break;  // As long as users go to the VIP window to handle business, they will jump out of the cycle to avoid bugs
}
} else break;
}
}
for (int i = 0; i < n2; i++) {  // Traverse from the smallest Window
if (team.size() == 0) break;  // If there is no one in the team, jump out of the cycle to prevent error reporting
if (win[i] == 0) {  // As long as no one is using the window, let the first user in the team handle business
for (int j = 0; j < (int)team.size(); j++) {
if (team[j].GetTime <= now_time) {
win[i] += team[j].SpendTime;  // ditto
win_count[i]++;
avg_time += (now_time - team[j].GetTime);
if (now_time - team[j].GetTime > long_time) long_time = now_time - team[j].GetTime;
team.erase(team.begin());
break;
} else break;
}
}
}
int tag = 0;  // In order to count the total consumption time, the loop will jump out only when the time of all windows is 0
for (int i = 0; i < n2; i++) {
if (win[i] > 0) {
win[i]--;
}
if (win[i] > 0) tag = 1;
}
now_time++;
if (tag == 0 && team.size() == 0) break;

}
printf("%.1f %d %d\n", (avg_time * 1.0) / n, long_time, now_time);
for (int i = 0; i < n2; i++) {
if (i != 0) printf(" ");
printf("%d", win_count[i]);
}
}
```

Tags: C++

Posted by ztkirby on Sun, 15 May 2022 00:39:37 +0300