P8299 [COCI 2012/2013 #2] INFORMACIJE 详解

Cells · 2025-07-28 16:38:27 · 题解

思路

很不错的一道题。

先看看数据范围，在 O(n^3) 的时间复杂度内都是能接受的。

走构造这条路半天走不通，果断换方向。

根据题目的限制条件，每个位置都能处理出来它能够填的数的范围，这里可以直接暴力去做，时间复杂度 O(m n ^ 2)。

想到这一步，你只差临门一脚了，在看下面的题解之前我劝你再想想。

因为每个位置都对应一个数，所以我们只需要跑二分图最大匹配就可以了。

判断无解的话，你可以看最大匹配的数量是否等于 n，如果不相等说明有的位置没有值，不行。

当然，在这道题我们可以用匈牙利算法。

考虑优化 O(m n^2) 建图。

发现对于一类区间（最大值和最小值），这里我举最大值的例子，我们按照 v 降序排序，从前往后扫，在线段上的对应区间上直接推平成 v（因为每个位置的上界就是覆盖它的区间中最小的最大值，按照降序排序的原因），这样就得到了上界，下界同理，可以优化至 O(m \log{m})。

或者还是最大值的例子，按照将区间左端点排序，遍历每个位置，如果碰到左端点，则将 v 加入堆中，这个位置的上界就是当前堆中的最小值，若是右端点（准确来说是右端点加一，因为右端点也是可以造成贡献的），利用 可删堆 删除，时间复杂度 O(m \log{m})。