※ 引述《Pttgambler ( )》之铭言：
: 最近在 Leetcode 上面看到有人分享的一题线上测验，
: 想了一段时间都没有想出暴力解以外的做法，所以来这里问看看。
: https://leetcode.com/discuss/interview-question/4902893/recent-goldman-sachs-oa-questionanybody-with-a-optimal-approach
: In a tranquil village school, there are two students named Ramu and Sonu,
: each possessing a collection of N distinct chalks. Each student's chalks are
: of different lengths, represented by N positive integers. Ramu has arranged
: his collection of N chalks in a specific order based on their lengths. Sonu
: is eager to organize his own N chalks in a way that mimics Ramu's arrangement
: in terms of length changes i.e. if in Ramu's arrangement the kth chalk is
: bigger than the k+1th chalk, in Sonu's arrangement also the kth chalk will be
: bigger than the k-1th chalk; alternately if it is smaller in Ramu's
: arrangement, then it will be smaller in Sonu's as well.Sonu was busy
: arranging his chalks, when his teacher told him to also maximize the overall
: "niceness" of his arrangement. Here, niceness' is defined as the sum of the
: absolute length differences between all adjacent chalks in the
: arrangement.Write a program to assist Sonu in achieving both the objectives:
: first, to mimic Ramu's length variation order, and second, to maximize the
: overall niceness of the arrangement.
: Sample Input1:
: 4
: 5 7 4 9
: 1 2 3 4
: Sample Output1:
: 7
: Explanation1:
: Given N=4.
: Ramu's chalks are arranged in the order of their length as 5 7 4 9, which
: corresponds to an increase- decrease-increase pattern of arrangement. Sonu
: has the chalk collection 12:34.
: To mimic Ramu's chalk arrangement order of increase-decrease-increase, Sonu
: can arrange his chalk in the following five ways.
: (1,3,2,4)-niceness-> |1-3|+|3-2|+|2-4|=2+1+2=5
: (1,4,2,3)-niceness-> |1-4|+|4-2|+|2-3|=3+2+1=6
: (2,3,1,4)-niceness-> |2-3|+|3-1|+|1-4|=1+2+3=6
: (2,4,1,3)-niceness-> |2-4|+|4-1|+|1-3|=2+3+2=7
: (3,4,1,2)-niceness-> |3-4|+|4-1|+|1-2|=1+3+1-5
: As can be seen, the maximum niceness possible is 7, which is printed as
: output.
令两个输入为数列 a[] 和 b[]
令最佳的 b[] 顺序为 B[] // sorted(b) == sorted(B)
// answer == niceness(B)
niceness(B) 是阵列中相邻两个数的差，对每个 B[i] ，有三个 case:
1. B[i] is a local maximum:
计算 niceness 时，会算到 (B[i] - B[i + 1]) + (B[i] - B[i - 1])
只考虑 B[i] 的贡献的话，就是 2*B[i] 或是 B[i] (B[i-1], B[i+1] 可能不存在)
2. B[i] is a local minimum:
和前一个状况对称，B[i] 的贡献是 -2*B[i] 或是 -B[i]
3. 其他
- B[i-1], B[i+1] 一定都存在
- B[i-1] < B[i] < B[i+1] 或 B[i+1] < B[i] < B[i-1] 洽有一个成立
计算 niceness 时，会算到 (B[i] - B[i-1]) + (B[i+1] - B[i]) 或是
(B[i] - B[i+1]) + (B[i-1] - B[i])
==> B[i] 对 niceness 没有贡献
我们先用 a 找到 local maximum 的位置 M[] 和 local minimum 的位置 m[]
假设我们已经找到排列 B ，则:
def niceness(B: int[], M: int[], m: int[]):
val = 0
for i in M:
if i == 0 or i + 1 == len(B):
val += B[i]
else:
val += 2*B[i]
for i in m:
if i == 0 or i + 1 == len(B):
val -= B[i]
else:
val -= 2 * B[i]
return val
B[i] 只有五种可能的贡献方式:
1) 2 * B[i]
2) B[i]
3) 0
4) -B[i]
5) -2*B[i]
我们将 b 由大排到小，依序用 (1), (2), (3), (4), (5) 的方式贡献
这样算出来的 niceness 就会是最大值
def cmp(x, y):
if x < y:
return -1
if x > y:
return 1
raise ValueError('There are duplicated values')
def solve(n, a, b):
c = [0] * n
for i in range(n):
if i > 0:
c[i] += cmp(a[i], a[i-1])
if i + 1 < n:
c[i] += cmp(a[i], a[i+1])
b = sorted(b)
c = sorted(c)
return sum(b[i] * c[i] for i in range(n))
证明这样的 B 是存在的：
我们先把 b 照大小排列，依照 (1), (2), (3), (4), (5) 分组
(1) b[0] > b[1] > b[2] > b[3] > ...
(2) b[k] // 也可能不存在，也可能有两个数
(3) b[k+1], b[k+2], ..., b[l-1]
(4) b[l] // 也可能不存在，也可能有两个数
(5) b[l+1] > b[l+2] > ... > b[n-1]
这样一定可以满足：(1), (2) 的任意值 > (3) 的任意值 > (4),(5) 的任意值
b[k], b[l] 会被放在 b[0] 或 b[n-1] 的位置
而其他位置的极值可以分别从 (1) 和 (5) 任选
在 a[] 中，极大值和极小值一定是依序出现的，
极大值跟极小值中间可以间隔数个中间值，
我们可以从 (3) 里面依序挑出足够的数量，并用正确的顺序放入就可以了
用这种方式构造出来的 B 一定可以满足条件
(i) B[i], B[i+1] 的相对大小和 a[i], a[i+1] 一样
(ii) B 的 niceness 是最大值
我把讨论串里面的几组测资打进去答案都一样，希望没有漏掉什么