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

· · 题解

读完题很容易想到这是一道贪心题。问题在于怎么个贪法。

91 分做法：

要贪心就要先把小朋友们的座位区间进行排序。排序规则是先按右边界从小到大排序，如果相同就把左边界从大到小排序。这样我们每次都会优先处理座位区间最短的小朋友，使我们可选的座位最大。

根据上面这个思路，很容易就写出了如下代码：

for (int i=1; i<=n; i++)
{
    memset(seat,0,sizeof(seat));
    int cnt = 0;
    for (int j=1; j<=m; j++)
    {
        for (int k=a[j].l; k<=min(a[j].r,i); k++)
        {
            if (!seat[k])
            {
                seat[k] = 1;
                cnt++;
                break;
            }
        }
    }
    cout << cnt << '\n';
}

因为题目让我们分别求座位数 k=1 \to n 的最大值，对于每个 k，会让学生的可选区间发生变动。也就是说，如果一个学生的座位区间是 l \to r，但假如此刻的 k ＜r，那么这位同学的可选区间实际上是 l \to k，这就导致我们记录座位占用情况的数组 seat[\ ] 每次都要清零，从头来过。这会导致算法效率奇低无比，时间复杂度将会达到 \operatorname{O}(n^2\times m)。很显然对于本题的数据范围 n,m \le 2×10^5 是无法通过的。但是为了验证贪心的正确性，我还是提交了一次，没想到直接拿到了 91 分，对于 n,m \le 5000 的情况都可以得到正确结果。

100 分做法：

既然贪心思路没问题，接下来考虑怎么优化算法。

对于查找可以坐的座位时，原算法是枚举 l \to r 之间可以坐的位置。对于这步，可以使用并查集来维护每个座位的是否可用。

初始时，每个座位的父节点指向自己。根据前文提到 k 的特性，即每个同学实际可选座位是 l \to \min(r,k)，所以在选择座位时，优先查看左区间，如果可用，则占用该座位，可坐人数 +1，并更新并查集，让被占据座位的父亲节点更新为下一把可用的椅子。这样就使得下次查找时跳过已被占用的座位，同时，还能在 \operatorname{O}(m\timesα(n)) 的时间复杂度内完成所有计算，其中α是阿克曼函数的反函数，可以视为常数。

核心代码：

// 初始化并查集
for (int i = 0; i <= n + 1; i++)
    parent[i] = i;

// 处理每个区间
for (int i = 0; i < m; i++) 
{
    int l_val = a[i].l;
    int r_val = a[i].r;
    int s = find(l_val); // 找到当前可用的最大座位
    if (s >= l_val && s <= r_val) 
    { // 确保座位在有效范围内
        cnt[s]++; // 占用该座位
        parent[s] = find(s + 1); // 更新并查集，指向下一个可用座位
    }
}

在输出的时候，通过前缀和数组记录每个 k 的答案，即前 k 个座位中被占用的座位数。

// 计算前缀和
int current = 0;
for (int k = 1; k <= n; k++) 
{
    current += cnt[k];
    ans[k] = current;
}
// 输出结果
for (int k = 1; k <= n; k++) 
    cout << ans[k] << "\n";

排序算法是 \operatorname{O}(m\times \log m)，读入是 \operatorname{O}(m)，输出是 \operatorname{O}(n)，所以最终算法时间复杂度从 \operatorname{O}(n^2\times m) 优化到了 \operatorname{O}(n+m \times \log m)。

这样这道题就完美解决了！