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

赛场安排 比赛使用 OMS 监考系统,需要将参赛队员安排到系统中的虚拟赛场里,并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们,以便…

赛场安排

比赛使用 OMS 监考系统,需要将参赛队员安排到系统中的虚拟赛场里,并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们,以便发放比赛账号。为了尽可能减少教练和监考的沟通负担,我们要求赛场的安排满足以下条件:

- 每位监考老师负责的赛场里,队员人数不得超过赛场规定容量 C;

- 每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练,且每个赛场的监考老师都不相同,为此我们设计了多轮次排座算法,按照尚未安排赛场的队员人数从大到小的顺序,每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n;

- 如果 n ≥ C,则将其中 C 人安排到当前为空的编号最小的赛场,剩下的人继续按人数规模排队,等待下一轮处理;

- 如果 n < C,则寻找剩余空位数大于等于 n 的编号最小的赛场,将队员安排进去;

- 如果 n < C,且找不到任何非空的、剩余空位数大于等于 n 的赛场了,则新开一个赛场,将队员安排进去。

由于近年来参赛人数快速增长,2023年超过了 410 所学校 1.6 万人,所以我们必须写个程序来处理赛场安排问题。

时间限制:6000,内存限制:65536

输入

输入第一行给出两个正整数 N 和 C,分别为参赛学校数量和每个赛场的规定容量,其中 0 < N ≤ 5000,10 ≤ C ≤ 50。

随后 N 行,每行给出一个学校的缩写(为长度不超过 6 的非空小写英文字母串)和该校参赛人数(不超过 500 的正整数),其间以空格分隔。题目保证每所学校只有一条记录。

输出

按照输入的顺序,对每一所参赛高校,在一行中输出学校缩写和该校需要联系的监考人数,其间以 1 空格分隔。 最后在一行中输出系统中应该开设多少个赛场。

样例输入

10 30
zju 30
hdu 93
pku 39
hbu 42
sjtu 21
abdu 10
xjtu 36
nnu 15
hnu 168
hsnu 20

样例输出

zju 1
hdu 4
pku 2
hbu 2
sjtu 1
abdu 1
xjtu 2
nnu 1
hnu 6
hsnu 1
16
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//答案来源于AI #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; #include &lt;set&gt; #include &lt;algorithm&gt; #include &lt;cctype&gt; #include &lt;string&gt; using namespace std; struct School {     string name;     int total;     int remaining;     int supervisors;     School(string n, int t) : name(n), total(t), remaining(t), supervisors(0) {} }; int main() {     int N, C;     cin &gt;&gt; N &gt;&gt; C;     vector&lt;School&gt; schools;     for (int i = 0; i &lt; N; i++) {         string name;         int num;         cin &gt;&gt; name &gt;&gt; num;         schools.push_back(School(name, num));     }     auto cmp = [](const pair&lt;int, int&gt;&amp; a, const pair&lt;int, int&gt;&amp; b) {         if (a.first != b.first)              return a.first &lt; b.first;         else              return a.second &gt; b.second;     };     priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, decltype(cmp)&gt; pq(cmp);     for (int i = 0; i &lt; schools.size(); i++) {         pq.push({schools[i].remaining, i});     }     int totalRooms = 0;     vector&lt;set&lt;int&gt;&gt; buckets(51);     while (!pq.empty()) {         int remaining = pq.top().first;         int idx = pq.top().second;         pq.pop();         if (remaining &gt; schools[idx].remaining) {             continue;         }         if (remaining &gt;= C) {             totalRooms++;             schools[idx].supervisors++;             schools[idx].remaining -= C;             if (schools[idx].remaining &gt; 0) {                 pq.push({schools[idx].remaining, idx});             }         } else {             bool found = false;             for (int r = remaining; r &lt;= 50; r++) {                 if (!buckets[r].empty()) {                     found = true;                     int room_id = *buckets[r].begin();                     buckets[r].erase(room_id);                     int new_r = r - remaining;                     if (new_r &gt; 0) {                         buckets[new_r].insert(room_id);                     }                     schools[idx].supervisors++;                     break;                 }             }             if (!found) {                 totalRooms++;                 schools[idx].supervisors++;                 int new_r = C - remaining;                 if (new_r &gt; 0) {                     buckets[new_r].insert(totalRooms - 1);                 }             }         }     }     for (int i = 0; i &lt; N; i++) {         cout &lt;&lt; schools[i].name &lt;&lt; " " &lt;&lt; schools[i].supervisors &lt;&lt; endl;     }     cout &lt;&lt; totalRooms &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。