※ 引述《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 是最大值
我把討論串裡面的幾組測資打進去答案都一樣，希望沒有漏掉什麼