A25061. 智能陪护
填空题
困难
知识点
题目描述
智能陪护
题目描述
智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选，当有老人下单时，系统自动将队列最前面的机器人派送给老人，该机器人就在老人下单的当天上岗了。当老人结算时，这个机器人就立刻结束任务，回到队列末尾排队等待下一次任务，必要时可以在当天就开始接任务。
本题就请你实现这样一个自动分配功能。
输入
输入在第一行中给出 2 个正整数：N（≤ 104）是机器人护工的数量—— 这里假设所有机器人护工从 1 到 N 编号，且一开始按照编号升序在系统队列中排队；K（≤ 105）是系统订单信息的条数。随后 K 行，每行给出一条订单信息，格式为： 老人ID 指令 日期 其中 老人ID是一个长度不超过 5 的字符串，由英文小写字母和数字组成；指令 为 1 表示下单，为 0 表示结算；日期是按照 年年年年月月日日 格式给出的，保证是一个 2022 年 1 月 1 日到 3022 年 12 月 31 日 之间的合法日期。 题目保证所有数据合理，即对每位老人，结算一定发生在下单之后，结算了一单才允许下另一单，且不存在只有下单没有结算、或只有结算没有下单的数据。
输出
按照下单的时间顺序，输出机器人护工的分配信息，每行输出一条，格式为： 老人ID - 机器人护工编号 如果同一天有多位老人下单或结算，保证先处理结算的，使得机器人能及时回到队列。对于同时下达相同指令的，则按照老人ID的升序排队处理。如果一位老人下单时，系统中没有机器人护工了，则需要等待。如果到老人结算时，都没有等到一位护工，则对应输出 老人ID - NONE 最后在一行中顺序输出队列中的机器人护工的编号。要求数字间以 1 个空格分隔，行首尾不得有多余空格。
样例输入
3 10
a01 0 20220202
a04 1 20220103
a02 1 20220101
a05 0 20220202
a03 1 20220101
a03 0 20220202
a04 0 20220201
a02 0 20220102
a05 1 20220101
a01 1 20220101样例输出
a01 - 1
a02 - 2
a03 - 3
a05 - 2
a04 - NONE
1 3 2参考答案
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int K = 1e5 + 10;
int n, k;
queue<int> que;
struct Order {
string name;
int type, dt;
bool operator<(const Order& o) const {
if (dt != o.dt) return dt < o.dt;
if (type != o.type) return type < o.type;
return name < o.name;
}
friend ostream& operator<<(ostream& out, const Order& o) {
out << o.name << " " << o.type << " " << o.dt;
return out;
}
} orders[K];
unordered_map<string, int> mp;
queue<Order> wt_que;
unordered_map<string, bool> waiting;
int _ = []() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
return 0;
}();
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) que.push(i);
for (int i = 0; i < k; ++i) {
cin >> orders[i].name >> orders[i].type >> orders[i].dt;
}
sort(orders, orders + k);
for (int i = 0; i < k; ++i) {
const Order& u = orders[i];
// cout << u << "\n";
if (u.type) {
if (!que.empty()) {
mp[u.name] = que.front();
cout << u.name << " - " << que.front() << '\n';
que.pop();
} else {
wt_que.push(u);
waiting[u.name] = true;
}
} else {
if (mp.find(u.name) != mp.end()) {
while (!wt_que.empty() && !waiting[wt_que.front().name]) wt_que.pop();
if (!wt_que.empty()) {
const Order& v = wt_que.front(); wt_que.pop();
mp[v.name] = mp[u.name];
cout << v.name << " - " << mp[u.name] << '\n';
} else que.push(mp[u.name]);
mp.erase(u.name);
} else {
cout << u.name << " - NONE\n";
waiting[u.name] = false;
}
}
}
while (!que.empty()) {
cout << que.front(); que.pop();
cout << (que.empty() ? "\n" : " ");
}
return 0;
}
上一题
下一题