2 回答

TA貢獻1848條經驗 獲得超2個贊
據我了解這個問題,要求是根據分數對學生進行排序,但還有一個額外的限制是要保留一個區域內學生的相對順序。
鑒于問題中列出的示例之一的輸入數據,
Region1:
A, 11.5
B, 8.5
C, 10.0
Region2:
D, 12.0
E, 9.0
F, 9.5
僅按分數排序會得出以下結果:DACFEB。
然而,關于在一個區域內保持相對排序的約束需要以下部分排序A < B < C 和 D < E < F。
OP 將此特定示例的解決方案稱為 DAEBCF。在對該問題的評論中,我為此示例提出了另外兩種可能的解決方案:DABCEF 和 DAEFBC。我沒有看到任何標準可以讓我們決定哪些可能的解決方案是正確的。因此,該問題受到了不足的約束。人們可以爭論這些解決方案中的哪一個比其他解決方案更可取,但這樣做會引入新的約束,而這些約束在原始問題中并不明顯。
鑒于有多個解決方案滿足問題中的所有標準,這意味著該域中的值沒有完全排序。此外,鑒于正確的比較器必須對其域的值進行總排序,因此不可能為該域編寫適當的比較器。
當然,可以編寫一個正確的比較器,它有一些行為,并且會更喜歡這些可能的解決方案之一而不是其他解決方案。這樣做將隱含地實施不屬于問題陳述的附加約束。事實上,Vincent van der Weele似乎已經這樣做了。語句“下一個空白點必須由其中一個區域的排名最高的剩余元素填充。哪個?得分最高的那個”引入了附加約束。它導致了 OP 建議的排序 DAEBCF。雖然這是明智的,但它必然是“正確”的排序。
另一種算法可能如下。1)從一個空的結果列表開始,并按排名順序維護來自每個地區的學生列表。2) 找出剩下的得分最高的學生。3) 取該學生和同一區域內排名較高的學生,并將它們附加到結果中,保持相對順序。4) 重復直到沒有學生留下。
將此算法應用于示例輸入會產生 DABCEF。這是明智的,但方式不同。同樣,我們不知道這是否是“正確”的答案。
要么是編程競賽中的問題一開始就沒有明確說明,要么是競賽的問題陳述與 Stack Overflow 上 OP 的問題之間丟失了一些信息。

TA貢獻1946條經驗 獲得超3個贊
您的比較器不正確。您基本上說,如果學生來自同一地區,則按排名排序,否則按分數排序。但事實并非如此,如本例所示:
Region1:
A, 11.5
B, 8.5
C, 10.0
Region2:
D, 12.0
E, 9.0
F, 9.5
結果是
D, 12.0
A, 11.5
E, 9.0
B, 8.5
C, 10.0
F, 9.5
即,得分為 9.0 的 E 排在得分為 10.0 的 C 之前,即使他們來自不同的地區。
一個更簡單的算法,它確實有效:
逐個元素填充結果。下一個空位必須由其中一個區域中排名最高的剩余元素填充。哪一個?得分最高的那個。因此,從其區域中刪除該元素,將其添加到結果中,然后重復直到完成。
添加回答
舉報