PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 排列組合(?)的一題

看板Prob_Solve (計算數學 Problem Solving)作者stimim (史提米)時間1月前 (2024/03/29 19:45)推噓1(1推 0噓 4→)

留言5則, 2人參與討論串2/2 (看更多)

※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1711712753.A.A71.html