※ 引述《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 是最大值 我把讨论串里面的几组测资打进去答案都一样，希望没有漏掉什麽 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 104.133.122.86 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1711712753.A.A71.html