题解 P1561 【[USACO12JAN]爬山Mountain Climbing】

· · 题解

证明辅助思想#（其实是某神犇的题解）

  1. 设置集合F、M、S：先让F中奶牛的爬山，再让M中奶牛的爬山，最后让S中奶牛的爬山。

  2. 对第i件，若U[i]>D[i]，则归入S；若U[i]=D[i]，则归入M，否则归入F。

  3. 对F中的元素按U[i]升序排列，S中的按D[i]降序排列。

我们可以证明，本题的最优解即为max（总上山时间+最快奶牛下山时间，总下山时间+最快奶牛上山时间）

去掉S中第一个上山时间与F中最后一个下山时间后，记该时间段为t

易知在t任取一个时间点，没有点前只有上山，点后只有下山（或是相反），也不存在没有上山或下山；

若t中一直有牛下（上）山，则可知下（上）山时间恒定，此时使第一头牛上山（最后一头牛下山）时间最短可得到答案；

由于两种情况只能满足其中一种，所以要取max。

//代码就不打了，如果真要看的话可以查看我的博客http://www.cnblogs.com/wanglixin1/p/6534622.html