题目传送门
题意
每个奶牛有重量和力量，他么会叠在一起，每只奶牛的危险度为他上面的牛的之质量减去他的力量，让你给他们一个上下的关系，使最大的危险值最小，输出这个危险值。
解题方法
我们考虑两个相邻的奶牛
i
i
i 和
j
j
j ，他们上面的牛的质量为
G
G
G 。 那么如果
i
i
i 奶牛在上面的时候危险度分别为 :
G
−
s
i
和
G
+
w
i
−
s
j
G-s_i和G+w_i-s_j
G−si和G+wi−sj 那么如果
j
j
j 奶牛在上面的时候危险度分别为 :
G
−
s
j
和
G
+
w
j
−
s
i
G-s_j和G+w_j-s_i
G−sj和G+wj−si 那么就需要比较上面的两个的最大值就可以了，最终得出的式子使当
w
i
+
s
i
<
w
j
+
s
j
w_i+s_i<w_j+s_j
wi+si<wj+sj为较优的结果，所以我们只需要以
w
i
+
s
i
w_i+s_i
wi+si为关键字排序，然后计算最大值就可以了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
struct node
{
long long sum
;
long long w
,s
;
}a
[100000];
bool comp(node x
,node y
)
{
return x
.sum
<y
.sum
;
}
int main()
{
long long n
;
scanf("%lld",&n
);
for(long long i
=1;i
<=n
;i
++)
{
scanf("%lld%lld",&a
[i
].w
,&a
[i
].s
);
a
[i
].sum
+=a
[i
].w
+a
[i
].s
;
}
sort(a
+1,a
+n
+1,comp
);
long long ans
=-1e9;
int he
=0;
for(long long i
=1;i
<=n
;i
++)
{
ans
=max(he
-a
[i
].s
,ans
);
he
+=a
[i
].w
;
}
cout
<<ans
<<'\n';
return 0;
}
