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