题解 CF538H 【Summer Dichotomy】

小粉兔 · 2020-03-09 23:01:31 · 题解

也就是要把老师分成两组，满足每组的 [l_i, r_i] 的交集，“相加”后与 [t, T] 有交。

如果有三个老师的 [l_i, r_i] 两两无交集，那么就完蛋了，根本没法分组。

否则，如果我们考虑其中一组的人数为 n_1 = \min \{ r_i \}，另一组的人数为 n_2 = \max \{ l_i \}。

如果 n_1 \ge n_2，也就是所有老师的 [l_i, r_i] 两两有交的情况，那么这种情况下每个老师都可以任意选组。

如果 n_1 < n_2，那么这也是最“松”的一种方案了，如果 n_1 增大或 n_2 减小都会导致某个老师无法选组的情况。

那么，也就是说 n_1 只能减小，n_2 只能增大。

然而，现在 n_1 + n_2 还不一定满足在 [t, T] 内的情况。

所以如果 n_1 + n_2 < t，就只能增大 n_2；如果 n_1 + n_2 > T，就只能减小 n_1。

那么就可以算出最优的一个 n_1 和 n_2 的选取方案，再根据这个方案对老师进行一次二分图染色判定即可。

时间复杂度为 \mathcal O (n + m)，评测链接。