Geedy演算完美切割解難題Leetcode 2551 Put Marbles in Bags 要找到所有切割的最大和最小score，可以使用兩種方法：排序切割score（partition[i] = weights[i] + weights[i+1]）或使用堆（C++ priority_queue）。一旦score排序或存儲在堆中，就可以輕鬆識別最大和最小score。
--------------
The Greedy algorithm for solving the perfect partitioning problem "Put Marbles in Bags" in LeetCode 2551.
To find the maximum and minimum scores of all partitions, you can either sort the partition scores (partition[i] = weights[i] + weights[i+1]) or use heaps (a data structure). Once the scores are sorted or stored in a heap, it becomes easy to identify the maximum and minimum scores.
[codes on Leetcode]https://leetcode.com/problems/put-marbles-in-bags/solutions/3734243/explain-partition-c-python-greedy-sort-vs-priority-queue/
[LeetCode程式]https://www.youtube.com/watch?v=7g-E3d_Oja4&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk&index=1
 |
一個分割的基本意義是什麼？
分割指的是將某物（例如集合或陣列）分成獨立的部分或子集。
能否解釋如何基於分割中的權重找到 k-1 對？
要基於分割中的權重找到 k-1 對，我們需要確定分割中每個子陣列的結束索引。對於每個 i-th 子陣列（表示為 P[i]），我們觀察 weights[P[i]] 和 weights[P[i]+1] 元素。我們將這個過程應用於分割中的所有子陣列。
什麼是分割的分數？
分割的分數，表示為 score(P)，是通過對特定權重進行求和計算的。我們從 weights[0] 和 weights[n-1] 開始，然後對於每個子陣列 i，我們將 weights[P[i]] 和 weights[P[i]+1] 相加。這個總和在分割中的所有子陣列上重複。
score(P)=
(weights[0]+weights[P[0]])+(weights[P[0]+1]+weights[P[1]])+
⋯+(weights[P[i−1]+1]+weights[P[i]])+
⋯+(weights[P[k−2]+1]+weights[n−1])
=weights[0]+weights[n−1]+ ∑(weights[P[i]]+weights[P[i]+1])
看這個例子。用"|"表示分割。由於 k=4，恰好有 3 個分割。
[54,6,34,66,63|52,39,62,46,75,28,65,18,37,18|13,33,69,19,40,13|10,43,61,72]
P[0]=4，weights[P[0]]=63，weights[P[0]+1]=52，partition[0]=63+52
P[1]=14，weights[P[1]]=18，weights[P[1]+1]=13，partition[1]=18+13
以分割的分數為基礎，所期望的答案是什麼？
所期望的答案是所有分割的最大分數（maxP）與最小分數（minP）之間的差異。
最多可以有多少個分割？
最多可以有 n-1 個分割。
如何找到所有分割的最大和最小分數？
要找到所有分割的最大和最小分數，可以對分割分數進行排序（partition[i] = weights[i] + weights[i+1]）或使用堆（一種資料結構）。一旦分數被排序或存儲在堆中，就容易識別最大和最小分數。
沒有留言:
張貼留言