很容易看的出来是一个贪心。
首先对A,B数组进行排序。
我猜测的结论是每次从A数组和B数组中的两端选择,分别得到:
A的最左端 - B的最左端的值
A的最右端 - B的最左端的值
A的最左端 - B的最右端的值
A的最右端 - B的最左端的值
比较这四个值取最大的然后用双指针维护一下就可以了。
首先,为什么要排序:是为了帮助我们更好的去寻找这个剩余的数组中相差最大的值是多少。
其次,为什么要去找剩余数组中相差最大的值(事实表明,贪心的结论严格证明起来其实是非常困难的,这里我凭借感觉了):我们假设我们不选择相差最大的a 和 b,我们原本可以得到val = |a - b|,但是现在存在c使得|a - c| < |a - b|,我们如果选择c,那么剩下的n - 1的最优方案如果不选则b,那么我们一定可以选择b,所以b更加优秀。如果剩下的n - 1最优方案选择了b,也就是说有一个字母d选择了b
1.a < b
(1) a < c < d < b 那么我们按照策略获得val = b - a + d - c,val' = c - a + b - d。显然b + d > c + d, a + c < a + d, 所以val > val'
(2) a < d < c < b, val = b - a + c - d, val' = c - a + b - d, val = val'
2.a > b(省略)
Ca的思路并不是很严谨(是在乱搞),所以仅仅提供一种思维方式 Qwq)
标签:Different,val,Very,端的,选择,1921,数组,左端 From: https://www.cnblogs.com/ybC202444/p/17985959