AT_arc076_d题解

只需求不加椅子时最多能使多少人有椅子坐。 开始想了一种网络流做法: 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$ 更小的，不难发现这样是最优的。