編輯 ：
老師剛剛確認有一個錯誤，它是 O(mlogm) -___-
問題陳述
該演算法接收木板長度[ L0, ..., L_n-1 ]串列和所需切割件長度串列[M0, ..., M_m-1]。它回傳一個向量[P0, ..., P_m-1]，p_j其中j是切出木板的木板的索引。 P_j = -1如果那塊沒有被剪掉。
貪心演算法是：
選擇最大的一塊
j和最長的木板i；j從所需切割件串列中洗掉該件。如果
M_j > L_i，j則不切割。所以我們設定P_j = -1并回傳到步驟 1。我們
j從木板上切下一塊，i使其長度變為L_i - M_j。我們設定P_j = i;如果還有要切割的碎片，請回傳到步驟 1。
問題是O(m log n)使用堆及時實作這個貪心演算法。
它給出了m >= n。
題
所以我的問題是，使用堆并看到我們需要最大的一塊j和最長的木板i，有些東西告訴我我們需要對向量進行排序，因此我不知道我們如何在O(m log n).
有人可以啟發我如何及時完成O(m log n)嗎？
我認為堆的使用可以是 1 堆木板和 1 塊或只有 1 堆，但必須至少有一個堆。（所以一個堆不一定可以使用2）
uj5u.com熱心網友回復：
如果您將自己限制為基于比較的排序，那么我認為您不能做得比O(m log m)（比 差O(m log n)）。這是因為第一步（“選擇最大的塊 j”）有效地生成了長度已排序的塊序列m——正如您正確指出的那樣。
但是，O(m log n)如果您對塊使用線性時間排序（例如基數排序）M_j，對木板使用堆，則可以執行此操作L_i。那種碎片將需要O(m)。您將m在堆上執行push/pop 操作，其大小受板數的限制n。因此，該堆上的操作總計為O(m log n)。加上之前的排序，仍然是O(m log n).
uj5u.com熱心網友回復：
這個簡單的實作是 O(m log m)。這是不可避免的，因為該問題需要處理從大到小的切割。這需要對m元素進行排序，即 O(m log m)。沒有更快的排序演算法。
typedef std::pair<size_t,size_t> pss;
std::vector<int> greedy(const std::vector<size_t>& L, const std::vector<size_t>& M)
{
std::vector<int> result(M.size(), -1);
// heap of pairs that sorts on pair.first, top==largest element
std::priority_queue<pss> Lheap, Mheap;
// create heaps of value => index
for (size_t i = 0; i < L.size(); i)
Lheap.push(pss{L[i],i});
for (size_t i = 0; i < M.size(); i)
Mheap.push(pss{M[i],i});
// process cuts from largest to smallest
while (!Mheap.empty() && !Lheap.empty())
{
// take longest plank & cut
auto mi = Mheap.top();
auto li = Lheap.top();
Mheap.pop();
// check if cut is too big
if (mi.first > li.first)
continue;
// write plank index to cut index
result[mi.second] = li.second;
// update heap: remove old plank, reinsert with new length
Lheap.pop();
li.first -= mi.first;
if (li.first > 0)
Lheap.push(li);
}
return result;
}
僅當至少 M 個輸入向量被預先排序，那么 O(m log m) 成本當然會移至前提條件。在這種情況下，您只需要 Lheap，洗掉 Mheap 及其 O(m log m) 成本，您只需在 M 上進行迭代。因此，您最終得到 O(m log n)：m 次回圈迭代，Lheap 操作的成本為 O(log n)。
uj5u.com熱心網友回復：
在 O(n m) 時間內從 n 個木板長度和 m 個切割長度中構建最大堆（如果您一次構建所有元素而不是一次插入一個元素，則可以在 O(k) 時間內構建 k 個元素的堆時間，并且您將所有元素預先作為演算法的輸入，這就是可以在線性時間內構建堆的原因）。
現在，使用標準堆操作，您可以在 O(logm) 時間內從切割長度堆 MH 中移除切割長度，并且可以在 O(logn) 時間內從木板長度堆 LH 中移除木板長度時間。此外，您可以通過洗掉木板長度值來減少它，然后在 O(logn logn) = O(2logn) = O(logn) 時間內重新插入較小的值。
一個注意事項：在這些堆中，您需要將索引和長度存盤到原始陣列中。您的堆將按長度構造（頂部較長的長度），但堆的各個元素需要是結構/對/物件，它們在索引旁邊存盤切割/木板長度。如果您使用 cpp 對，您可以將長度放在第一位，然后將索引放在第二位，默認情況下堆將被正確排序（作為根據第一對元素排序的最大堆）。
重新審視演算法的步驟，看起來使用基于堆的方法可以實作的最佳復雜度是 O(mlogm) 時間：
查看 LH = {L_j, j} 和 MH = {M_i, i} 的頂部元素：O(1)
從 MH 中彈出 {M_i, i}：O(logm)
檢查最高切割長度 M_i 是否大于最高木板長度 L_j。如果 M_i > L_j，我們不能剪掉那個長度。設定 P[j] = -1 并回傳到步驟 1：O(1)
通過彈出LH（O（logn））并將{L_j - M_i，j}插入其中（也是O（logn）），從木板L_j切割長度M_i。設定 P[j] = i (O(1)): O(logn)
如果還有要切割的部分（如果 !MH.empty() && !LH.empty()），請回傳步驟 1：O(1)
每次執行回圈，我們都會做 log(m) log(n) O(1) = O(logm) 的作業。回圈最多運行 max(n,m) = m 次。所以整體復雜度是 O(n m mlogm) = O(mlogm)。你不能做得比這更好，除非 M 是預先排序的（在這種情況下你不需要 MH，而是可以只保留一個索引到 M 并且 O(logm) 步驟 2 可以替換為 O(1) {M_i, i} = M[mIdx ]，將整體復雜度降低到 O(m*logn))。
看起來另一個答案已經發布了這個演算法的實作，但我仍然會添加我的答案作為復雜性分析。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/374301.html
下一篇：2個節點碰撞的時間