n個有重複數，求其一種排列使得前綴和絕對值的最大值最小，有較好的演算法嗎？

12-31

如題。

我來解釋一下 @趙金昊構造的例子。

假設已知的數中有且僅有一個負數 -2N，另外的數都是正數，且和為 2N。

如果這些正數中有若干個相加等於 N，那麼就可以構造這樣一個排列：相加等於 N 的數排在前面，然後排 -2N，再把另外一些數排在後面。這樣，「前綴和的絕對值」最大是 N。

如果這些正數中沒有任意一個子集相加等於 N，則上面這件事做不到，「前綴和的絕對值」必然在某個時刻大於 N。

而「判斷一些數中有沒有一個子集相加等於給定值」（稱為「子集和問題」）是一個 NPC 問題，題主的問題可以化歸為子集和問題，所以沒有多項式時間的解。

補充一些細節。

首先證明「子集和問題」可以歸約為「均分問題」。子集和問題是給定 n 個正整數和一個正整數 m ，問能否從 n 個數中取出一些數使其和為 m 。用 (A, m) 表示子集和問題的輸入，其中 A 是長度為 n 的正整數列。

均分問題是給定 n 個正整數，問能否將這些數分成兩部分，使它們各自的和相等。用 A 表示均分問題的輸入，其中 A 是長度為 n 的正整數列。

注意均分問題顯然可以歸約為子集和問題（不過這不是我們需要的），但反過來則需要說明。任給一個子集和問題的輸入 I=(A, m) ，計算 A 中所有數之和 S ，將 J=A?{S+m+1, 2S-m+1} 作為均分問題的輸入，則 I 滿足子集和問題，當且僅當 J 滿足均分問題。這就完成了將子集和問題歸約為均分問題的過程。

接下來將均分問題歸約為題主所述的問題。題主的問題不是判定性問題，但是很容易找到相應的判定性問題：給定 n 個整數和一個整數 m ，問能否將 n 個數重排，使新數列前綴和絕對值的最大值小於等於 m 。不妨將該問題稱為「前綴和問題」。用 (A, m) 表示前綴和問題的輸入，其中 A 是長度為 n 的正整數列。

之後將均分問題歸約為前綴和問題，這個其他回答已經提到了。任給一個均分問題的輸入 I=A ，計算 A 中所有數之和 S ，將 J=(A?{-S}, S/2) （其中 S/2 取下整）作為前綴和問題的輸入，則 I 滿足均分問題，當且僅當 J 滿足前綴和問題。歸約過程完成。

因為子集和問題是 NPC 問題，所以前綴和問題是 NP-hard 問題（實際上前綴和問題也是 NP 問題，只要將 n 個數重排的順序作為證書即可；因此，前綴和問題是 NPC 問題），從而不太可能在多項式時間內解決。

題主的問題比「前綴和問題」（指剛剛提到的判定性問題）要強，因為若求得前綴和絕對值最大值的最小值，立即可以解決「前綴和問題」。所以題主的問題也不太可能在多項式時間內解決。

NPC的，別想啦。

搞個-2N，以及若干個和為2N的數，不是分分鐘變成子集和問題嘛。

所以解題思路只有一種，就是看數的大小。如果不超過10的話還是可做的……

數據範圍小的時候可以考慮暴搜O(n!)或者去dp一下——dp[現在已經用了哪幾個數]，保存值為前綴最大值O(2^n*n)。

既然是NPC那我就可以放心大膽推薦退火和遺傳了

感覺退火可做。