首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#7496

智能陪护 智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选,当有老人下单时,系统自动将队列最前面的机器人派送给老人,该机器人就在…

智能陪护

智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选,当有老人下单时,系统自动将队列最前面的机器人派送给老人,该机器人就在老人下单的当天上岗了。当老人结算时,这个机器人就立刻结束任务,回到队列末尾排队等待下一次任务,必要时可以在当天就开始接任务。

本题就请你实现这样一个自动分配功能。

时间限制:6000

内存限制:65536

输入

输入在第一行中给出 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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;algorithm&gt; #include &lt;unordered_map&gt; using namespace std; const int K = 1e5 + 10; int n, k; queue&lt;int&gt; que; struct Order {     string name;     int type, dt;     bool operator&lt;(const Order&amp; o) const {         if (dt != o.dt) return dt &lt; o.dt;         if (type != o.type) return type &lt; o.type;         return name &lt; o.name;     }     friend ostream&amp; operator&lt;&lt;(ostream&amp; out, const Order&amp; o) {         out &lt;&lt; o.name &lt;&lt; " " &lt;&lt; o.type &lt;&lt; " " &lt;&lt; o.dt;         return out;     } } orders[K]; unordered_map&lt;string, int&gt; mp; queue&lt;Order&gt; wt_que; unordered_map&lt;string, bool&gt; waiting; int _ = []() {     ios::sync_with_stdio(false);     cin.tie(NULL), cout.tie(NULL);     return 0; }(); int main() {     cin &gt;&gt; n &gt;&gt; k;     for (int i = 1; i &lt;= n; ++i) que.push(i);     for (int i = 0; i &lt; k; ++i) {         cin &gt;&gt; orders[i].name &gt;&gt; orders[i].type &gt;&gt; orders[i].dt;     }     sort(orders, orders + k);     for (int i = 0; i &lt; k; ++i) {         const Order&amp; u = orders[i];         // cout &lt;&lt; u &lt;&lt; "\n";         if (u.type) {             if (!que.empty()) {                 mp[u.name] = que.front();                 cout &lt;&lt; u.name &lt;&lt; " - " &lt;&lt; que.front() &lt;&lt; '\n';                 que.pop();             } else {                 wt_que.push(u);                 waiting[u.name] = true;             }         } else {             if (mp.find(u.name) != mp.end()) {                 while (!wt_que.empty() &amp;&amp; !waiting[wt_que.front().name]) wt_que.pop();                 if (!wt_que.empty()) {                     const Order&amp; v = wt_que.front(); wt_que.pop();                     mp[v.name] = mp[u.name];                     cout &lt;&lt; v.name &lt;&lt; " - " &lt;&lt; mp[u.name] &lt;&lt; '\n';                 } else que.push(mp[u.name]);                 mp.erase(u.name);             } else {                 cout &lt;&lt; u.name &lt;&lt; " - NONE\n";                 waiting[u.name] = false;             }         }     }     while (!que.empty()) {         cout &lt;&lt; que.front(); que.pop();         cout &lt;&lt; (que.empty() ? "\n" : " ");     }     return 0; }</pre>
这道题暂未补解析。