题解：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 的情况下代替单调队列，啊？

Code

CPP

#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;
}

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

文章操作

思路

相关推荐

评论

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