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

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

看板Prob_Solve (計算數學 Problem Solving)作者Pttgambler (　)時間7月前 (2024/03/29 12:31)推噓0(0推 0噓 0→)

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

最近在 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. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.138.126.248 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1711686700.A.EAA.html ※ 編輯: Pttgambler (220.138.126.248 臺灣), 03/29/2024 12:33:11