AT_arc076_d题解

PenguinJ · 2025-08-04 16:34:09 · 题解

只需求不加椅子时最多能使多少人有椅子坐。 开始想了一种网络流做法: 1.源点向每个人连一条容量为 1 的边。 2.由于每个人有两种坐法，坐在 L_i 及其左边的椅子或坐在 R_i 及其右边的椅子，可以考虑把每个椅子拆成 3 个点，将拆出来的点划分为三个部分，第 i 个人向第一部分的点 L_i 连边,向第二部分的点 R_i 连边。第一、二部分的点再分别向第三部分的点连边。第三部分的点分别向汇点连一条容量为 1 的边。 3.对于一个人，如果他能坐椅子 L_i ，那么编号小于 L_i 的椅子他也能坐， 所以对于第一部分的点 i ，应向点 i-1 连边。第二部分的点同理。 之前看到一个ID算法，时间复杂度为 O(km) ，应该能过，但我不会。

所以还是想有没有直接的贪心做法： 发现最后椅子的分配一定是左边若干个分配给某些人左区间，中间若干把无法分配，其余右边的椅子分配给某些人的右区间，因为靠左的椅子分配给右区间，靠右的分配给左区间，交换它们的分配方式仍然合法。 对每个人按 L_i 升序排序，按编号从小到大枚举椅子，分配给可以分的人的左区间，剩下的椅子尽量分给每椅子的人中 R_i 更小的，不难发现这样是最优的。