题解：B4160 [BCSP-X 2024 12 月小学高年级组] 排座位

· · 题解

去年赛场上果断放弃了，今年看起来就还行了，想了 1h 勉强切掉了。

写一篇较为详细的题解。

思路

首先，这种区间的玄学题目一般都是贪心。而它又需要给出对于 1\sim n 每一个数的答案，这暗示我们应该从左往右扫一遍统计答案。

首先考虑朴素贪心。很难容易发现，对于每一个座位，总是满足条件 r_i 最小的人，这是为了给后面的座位更多的选择。所以我们只需要对于每一个座位，扫一遍 n 个人就可以。

时间复杂度 O(nm)。

考虑优化，观察算法标签，可以发现应该使用单调队列，然而一个人安排一次就不能再用了，所以单调队列我不太会做。

发现优先队列可以做，因为每次用完就扔掉就可以了。

具体来说，i=1\sim m 扫一遍：每次将左端点为 i 的人入队。此时，将队首不满足条件的全部丢掉（毕竟一定满足 r_i < i，所以之后也一定没用）。若队列不空，把队首用掉，统计答案即可。

由于每个人只会进队一次，所以时间复杂度 O(n\log n)，这个题就做完了。

突然发现优先队列可以在多一个 log 的情况下代替单调队列，啊？

::::success[Code]

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 2e5 + 5;
struct Range
{
    int l, r;
} p[N];
priority_queue<int, vector<int>, greater<int> > q;

bool cmp(Range x, Range y)
{
    return x.l < y.l;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> p[i].l >> p[i].r;
    sort(p + 1, p + m + 1, cmp);
    int cnt = 1, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        while (p[cnt].l == i && cnt <= m) q.push(p[cnt++].r);
        while (!q.empty() && q.top() < i) q.pop();
        if (!q.empty())
        {
            q.pop();
            ans++;
        }
        cout << ans << endl;
    }

    return 0;
}

::::