L2-046 天梯赛的赛场安排

思路

• 模拟整个过程
• 用优先队列保证，每次处理的是人数最少的学校
• 注意一个点，当第二种情况发生的时候，此时这个赛场不可能又当前学校的队员，所以对当前学校来说，这个教室也是新开的

#include <bits/stdc++.h>
//#define int long long
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
map<string, int> ans;
vector<int> room; // 记录每个赛场剩余位置
vector<string> order; // 记录学校的输入顺序
struct node
{
    string name;
    int cnt; // 剩余人数
    bool operator < (const node& t) const
    {
        return cnt < t.cnt;
    }
};
priority_queue<node> q;
signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        string name;
        int cnt;
        cin >> name >> cnt;
        // 记录学校顺序
        order.push_back(name);
        q.push({name, cnt});
    }
    while(q.size())
    {
        int cnt = q.top().cnt;
        string name = q.top().name;
        q.pop();

        if(cnt >= m)
        {
            room.push_back(0);
            ans[name] ++;
            if(cnt > m) q.push({name, cnt - m});
        }
        else
        {
            int ff = 0;
            for(int i = 0; i < room.size(); i ++)
            {
                if(room[i] >= cnt)
                {
                    room[i] -= cnt;
                    ans[name] ++;
                    ff = 1;
                    break;
                }
            }
            if(ff == 0)
            {
                room.push_back(m - cnt);
                ans[name] ++;
            }
        }
    }
    for(int i = 0; i < order.size(); i ++)
    {
        string name = order[i];
        cout << name << ' ' << ans[name] << endl;
    }
    cout << room.size() << endl;
    return 0;
}