18105 银行的叫号顺序
### 详细分析
为了模拟银行的叫号过程,我们可以使用优先队列(堆)来管理客户的服务顺序。优先级越高的客户会先得到服务,同级别的客户按到达时间先后顺序得到服务。如果优先级和到达时间都相同,则按输入顺序服务。
### 思路
1. **优先队列**:使用优先队列来管理客户,优先级高的客户先服务,同级别的客户按到达时间先后顺序服务。如果优先级和到达时间都相同,则按输入顺序服务。
2. **模拟服务过程**:每5分钟服务一个客户,如果没有客户则等待5分钟。
3. **输入处理**:读取输入的客户信息,并按到达时间排序。
### 伪代码
```plaintext
function serve_customers(n, customers):
priority_queue = empty priority queue
current_time = 0
customer_index = 0
while customer_index < n or not priority_queue.empty():
while customer_index < n and customers[customer_index].arrival_time <= current_time:
priority_queue.push(customers[customer_index])
customer_index += 1
if not priority_queue.empty():
customer = priority_queue.pop()
print(customer.name)
current_time += 5
```
### C++代码
#include <iostream>
#include <queue>
#include <vector>
#include <string>using namespace std;struct Customer {int arrival_time;int priority;string name;int index;bool operator<(const Customer& other) const {if (priority == other.priority) {if (arrival_time == other.arrival_time) {return index > other.index;}return arrival_time > other.arrival_time;}return priority < other.priority;}
};int main() {int n;scanf("%d", &n);vector<Customer> customers(n);for (int i = 0; i < n; ++i) {cin >> customers[i].arrival_time >> customers[i].priority >> customers[i].name;customers[i].index = i;}priority_queue<Customer> pq;int current_time = 0;int customer_index = 0;while (customer_index < n || !pq.empty()) {while (customer_index < n && customers[customer_index].arrival_time <= current_time) {pq.push(customers[customer_index]);customer_index++;}if (!pq.empty()) {Customer customer = pq.top();pq.pop();cout << customer.name << endl;}current_time += 5;}return 0;
}