用於最小最大連續k分區的更快算法

從鏈接：

「假設非負數的一個給定的排列Š{S1，...，SN}和整數k 如何削減 s轉換k或更少。範圍，，以儘量減少所有範圍的最大總和？「

例如，

S = 1,2,3,4,5,6,7,8,9

K = 3

通過切割s轉換這些3個範圍，最大範圍的總和（8,9）是17，這是最小的可能。

1,2,3,4,5 | 6,7 | 8,9

在鏈路建議的算法運行在O（KN^2），並使用O（KN）的空間。有更有效的算法嗎？

這是一個動態編程問題。而不是以指數的時間運行，它將解決方案優化爲只有多項式時間。這非常好，所以我認爲你不必搜索「更高效」的解決方案 – 2013-02-02 07:13:22

好吧，顯然這是關閉的「離題」！？但無論如何它現在已經備份，我發現解決方案是二進制搜索答案。對不起，我忘了其中一個約束是所有整數的總和不會超過2^64。所以讓C =所有整數的累加和。然後，我們可以爲答案二進制搜索使用

bool isPossible(int x)

函數返回true，如果有可能與S分成具有最大分區總和小於X. isPossible（INT X）K分區可以在完成O（n）（通過添加從左到右的所有內容，如果它超過了x，則創建一個新的分區）。所以總的運行時間是O（n * log（s））。

2013-02-07 07:21:21

回答