P1561 [USACO12JAN] Mountain Climbing S
贪心思路
首先我们设 \(c_i\) 为第 \(i\) 头牛上山后又下山的时间。
那么有两种情况，我们分类讨论。
-
第 \(i\) 头牛上到山顶时，第 \(i-1\) 头牛还未下到山脚。
-
第 \(i-1\) 头牛下山完毕但第 \(i\) 头牛还在上山。
那么 \(c_i\) 的公式就是：
\[c_i=\max(c_{i-1},\sum_{j=1}^{i}a_j)+b_i \]其中的 \(c_{i-1}\) 对应的就是第一种情况，因为第 \(i\) 头牛的下山时间是第 \(i-1\) 头牛到山脚的时间，而 \(\sum_{j=1}^{i}a_j\) 对应的是第二种情况，以为第 \(i\) 头牛的下山时间取决于自己什么时候上山，但是这两种情况只有一种是对的，所以要取一下 \(\max\)，把对的那一种挑出来。最后把第 \(i\) 头牛的下山时间加上就是 \(c_i\) 了。
我们发现 \(c_i\) 一定是单调递增的，所以答案就是 \(c_n\)，我们要使 \(c_n\) 最小。考虑使用相邻交换法。
我们看第 \(i\) 头牛和第 \(i+1\) 头牛那头先上山，换句话说就是第 \(i+1\) 头牛是否要排在第 \(i\) 头牛的前面。我们设 \(x\) 为 \(\sum_{j=1}^{i-1}a_j\)。
如果不交换则的话（取 \(c{i+1}\)，因为 \(c_{i+1}>c_i\)）：
\[c_{i+1}=\max(c_i,x+a_i+a_{i+1})+b_{i+1} \]即：
\[c_{i+1}=\max(\max(c_{i-1},x+a_i)+b_i,x+a_i+a_{i+1})+b_{i+1} \]又即：
\[c_{i+1}=\max(c_{i-1}+b_i+b_{i+1},x+a_i+b_i+b_{i+1},x+a_i+a_{i+1}+b_{i+1}) \]同理，要是把第 \(i\) 头牛和第 \(i+1\) 头牛交换，那么就变成了：
\[c_{i+1}=\max(c_{i-1}+b_i+b_{i+1},x+a_{i+1}+b_i+b_{i+1},x+a_i+a_{i+1}+b_i) \]那么如果不交换，则：
\[\max(c_{i-1}+b_i+b_{i+1},x+a_i+b_i+b_{i+1},x+a_i+a_{i+1}+b_{i+1})\le\max(c_{i-1}+b_i+b_{i+1},x+a_{i+1}+b_i+b_{i+1},x+a_i+a_{i+1}+b_i) \]由于是比大小，所以可以把两边的 \(c_{i-1}+b_i+b_{i+1}\) 消掉：
\[\max(x+a_i+b_i+b_{i+1},x+a_i+a_{i+1}+b_{i+1})\le\max(x+a_{i+1}+b_i+b_{i+1},x+a_i+a_{i+1}+b_i) \]然后我们发现余下的式子中都有 \(x\)，所以：
\[\max(a_i+b_i+b_{i+1},a_i+a_{i+1}+b_{i+1})\le\max(a_{i+1}+b_i+b_{i+1},a_i+a_{i+1}+b_i) \]然后化简一下：
\[\max(b_i,a_{i+1})+a_i+b_{i+1}\le\max(b_{i+1},a_i)+b_i+a_{i+1} \]再化简：
\[\max(b_i,a_{i+1})-b_i-a_{i+1}\le\max(b_{i+1},a_i)-a_i-b_{i+1} \]变：
\[-\min(b_i,a_{i+1})\le-\min(b_{i+1},a_i) \]最后消掉符号，注意变号：
\[\min(b_{i+1},a_i)\le\min(b_i,a_{i+1}) \]于是我们简化完就是如果 \(\min(b_{i+1},a_i)\le\min(b_i,a_{i+1})\) 返回结果是真，那么就不交换第 \(i\) 头牛和第 \(i+1\) 头牛，是假就交换。
但是，这样真的对吗？真的是我们想象的那样吗？
不对，这样没有传递性。
我举个例子：
\(A\) 的组织能力=\(B\) 的组织能力
\(B\) 的个人能力=\(C\) 的个人能力
那么 \(A\) 的组织能力=\(C\) 的组织能力？
这道题是一个道理：
\(\min(b_2,a_1)\le\min(b_1,a_2)\)
\(\min(b_3,a_2)\le\min(b_1,a_3)\)
那么 \(\min(b_3,a_1)\le\min(b_1,a_3)\) 吗？
所以，公式要有传递性。
如何具有传递性呢？我们把牛分为 \(3\) 类：
- 上山比下山快的
- 上下山一样快的
- 下山比上山快的
我们假设目前只有第一类的牛，那么我们由公式推一下：
\[\min(b_{i+1},a_i)\le\min(b_i,a_{i+1}) \]\(a_i\le b_i\) 且 \(a_{i+1}\le b_{i+1}\)，所以我们只需要比较 \(a_i\) 和 \(a_{i+1}\)，具体证明的话我用的是枚举法，把所有关系枚举一下，这里就不一一列举了。
按照枚举法，我们可以证明出第二类牛随便排，第三类牛比较 \(b_i\) 和 \(b_{i+1}\)。
然后我们要证明这三类牛按什么样的方式出场可以保证传递性。
我只说第一类和第二类的证明方法，其余第二类和第三类还有第一类和第三类大家用同样的方式推一推就行。
我们把 \(a_i\)，\(a_{i+1}\)，\(b_i\)，\(b_{i+1}\) 这四个数想象成在数轴上的四个点， \(a_i<b_i\) 和 \(a_{i+1}=b_{i+1}\) 是两个限制。有了这两个限制，我们就可以把 \(4\) 个点变成 \(3\) 个点，因为 \(a_{i+1}=b_{i+1}\)，且 \(a_i\) 与 \(b_i\) 这两个点的顺序都是确定的。我们设 \(x=a_{i+1}=b_{i+1}\)。
点 \(x\) 一共有三种插法，插在点 \(a_i\) 前面，\(a_i\) 和 \(b_i\) 的中间，\(b_i\) 的后面。三种情况分别枚举，得到的答案都是：上山比下山快的牛要排在上下山一样快的的后边。
同理枚举第二类第三类还有第一类和第三类得出的顺序是：先是上山比下山快的牛，再是上下山一样快的牛，最后是下山比上山快的牛。
所以到此为止此题就可一AC了。
code
//思路难想，代码好编，毕竟是贪心
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
int x,y,z;
}a[25004];
int c[25004];
bool cmp(node b1,node b2){
if(b1.z==b2.z){
if(b1.z<0)return b1.x<b2.x;//单种排序
else return b1.y>b2.y;//单种排序
}else return b1.z<b2.z;//种类分
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
if(a[i].x<a[i].y)a[i].z=-1;//上山比下山快的
else if(a[i].x==a[i].y)a[i].z=0;//上下山一样快的
else a[i].z=1;//下山比上山快的
}
sort(a+1,a+1+n,cmp);
int sum=0;
for(int i=1;i<=n;i++){
sum+=a[i].x;
c[i]=max(c[i-1],sum)+a[i].y;//算结果
}
cout<<c[n]<<endl;
return 0;
}
标签：Mountain,le,头牛,min,P1561,max,USACO12JAN,上山,下山 From： https://www.cnblogs.com/StudytoFLY/p/17991371