题解 P1937 【[USACO10MAR]仓配置Barn Allocation】

Fading · 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]。

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

因此得证。