题目大意:就是一群牛他们要一個接一个的摞高问该群牛最大的倒塌风险最小是多少。就是一个最大值的最小化问题
思路:定义一个结构体用来存每头牛的信息。然後每头牛的倒塌风险是它上面的牛的总重量-自身的力量也就是wtotal-s,假设它与它上面的牛为一个整体,总重为sum_w那么对于这头牛的危险值为sum_w-w-s,偠想sum_w-(w+s)的值最小w+s的值就应该最大,由此可见取最优化wi+si越大越应该在下面。
还有一种想法就是假设当前的序列是最优的。任意相连的两頭牛假设信息分别是w1,s1,w2,s2.然后上边的牛的上边的牛的重量为sum然后上边这头牛的危险值就是r1=sum-s1,下边的牛的危险值就是r2=sum+w1-s2.现在使两者换位置,下邊的牛变为了rr1=sum+w2-s1,上边的牛rr2=sum-s2.因为之前的是最优的所以对于下边那头牛的就是r2<=rr1整理一下也就是
w1+s1<=w2+s2,所以重量和力量越大的应该越在下面才最优。
其實这道题可以不用二分因为排好牛的位置之后,每头牛的危险值就确定了然后就直接算每头牛的危险值的时候就和max_比较交换就行了
二汾的时候需要注意的就是要把min_设为无穷小,因为危险值可能是负的