自动搬运

查看原文

来自洛谷，原作者为

	Fading AFO

搬运于2025-08-24 21:32:06，当前版本为作者最后更新于2019-06-26 13:21:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

相信大家都猜得到解法：

将奶牛的路径转化为线段，以右端点为第一关键字，左端点为第二关键字，按第一关键字从小到大排序，若第一关键字相同则按第二关键字从大到小排序。

然后按序枚举线段，看看是否可以放（区间最小值$>0$），如果可以，则区间内所有的数$-1$，答案$+1$，用线段树维护区间最小值。

这为什么是对的呢？

第一个结论证明比较显然，左端点从大到小取最优(假设右端点全都是$r$)。

（因为从小到大取所占用的空间和一定$\geq$从大到小取所占用的空间和，而且从小到大取占用的区间$\in$从大到小取占用的区间）

然后我们证明第二个结论，右端点从小到大取最优。

可以用归纳法。

第一条线段一定要加入。

假设已经到了第$i$条线段，端点为$l_i,r_i$

如果没有冲突，直接算入答案。这样根据归纳假设是最优的。

但如果冲突了，设和第$j$条线段冲突（当然j不唯一）

如果$j$的右端点等于$i$的右端点，可以直接不选$i$（刚才的结论）

否则

 -------------             j
    ------------------     i

发现如果不选$j$，选择$i$，就会让$[l_i,r_i]$区间全部$-1$，$[l_j,r_j]$全部$+1$

但是发生冲突的区间是$[l_i,r_j]$，之后这段区间最小值依旧为$0$。

显然如果剩下的区间左端点$\leq l_i$，一定不满足条件，这和$[l_j,l_i-1]$的区间$+1$失去了效果。

所以这样对后续的影响可以看成$[r_j+1,r_i]$全部$-1$。

但如果不选$i$呢？

就毫无影响。

所以如果选择$i$，就白白浪费了区间$[r_j+1,r_i]$。

所以我们不选，一定更优。

因此得证。

综上，我们证明了贪心的正确性。