我在一次比賽中遇到了這個問題。我們給定了一個數字 N，我們需要構造一個大小為 N 的數組，該數組僅由 1 和 -1 組成，使得每對的乘積之和的值為最小且為正。即如果數組是 A 那么所有 1 <= i < j <= N 的總和 ( A[i] * A[j] ) 為最小值且為正數。例子：輸入 => 3輸出 => [1,1,1]解釋 - 所有可能的情況是：[1,1,1] = 3[1,1,-1] = -1[1,-1,-1] = - 1[-1,-1,-1] = 3因此所有組合和最小可能的正例是 3。我們怎樣才能找到這樣一個數組呢？我試圖找到一種模式，但沒有成功。
1 回答
拉風的咖菲貓
TA貢獻1995條經驗 獲得超2個贊
分析起來很簡單，不需要為它編寫程序。
讓我們注意一下：
(a1 + a2 + ... + an)^2 = (a1^2 + a2^2 + ... + an^2) + 2 * (a1a2 + a1a3 + ... + ana(n-1))
或者換句話說（這里無法很好地格式化它）：
(sum_{i}(ai))^2 = sum_{i}(ai^2) + 2 * sum_{1 <= i < j <= N}(ai * aj)我們在這里尋找sum_{1 <= i < j <= N}(ai * aj).
經過一些簡單的添加，我們得到：
sum_{1 <= i < j <= N}(ai * aj) = 1 / 2 * ((sum_{i}(ai))^2 - sum_{i}(ai^2))另請注意，sum_{i}(ai^2)是常數，因為它等于N（僅-1或1），因此解決方案是當(sum_{i}(ai))^2最小時，因此等于0，當偶數N時和1當奇數時。
解決方案：
對于偶數-時間和時間
N的任意排列。N / 21N / 2-1對于奇數-時間和時間或時間和時間
N的任意排列。(N - 1) / 21(N + 1) / 2-1(N - 1) / 2-1(N + 1) / 21
編輯 - 最小正和：
擁有以下基礎：
sum_{1 <= i < j <= N}(ai * aj) = 1 / 2 * ((sum_{i}(ai))^2 - sum_{i}(ai^2)) = 1 / 2 * ((sum_{i}(ai))^2 - N)我們需要找到 ai，這樣(sum_{i}(ai))^2 > N => sum_{i}(ai) > sqrt(N).
如果我們有ceil(sqrt(N))時間1，我們必須N - ceil(sqrt(N)) = A在 之間進行分配1，并使-1它們的總和最小。解決方案很明顯：
對于
A = 2 * B=>B次1和-1.對于
A = 2 * B + 1=>B + 1times1和Btimes-1。
添加回答
舉報
0/150
提交
取消