自动搬运

查看原文

来自洛谷，原作者为

	wangxiaochai 老骥伏枥

搬运于2025-08-24 21:17:28，当前版本为作者最后更新于2025-02-25 21:03:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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)$。

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