构造大小为 N 的 1 和 -1 的数组 A，使得所有 A[i]*A[j] 的总和为最小值且为正数。

Question

我在一次比赛中遇到了这个问题。我们给定了一个数字 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。我们怎样才能找到这样一个数组呢？我试图找到一种模式，但没有成功。

Answer 1

分析起来很简单，不需要为它编写程序。

让我们注意一下：

(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当奇数时。

解决方案：

1. 对于偶数-时间和时间N的任意排列。N / 21N / 2-1

2. 对于奇数-时间和时间或时间和时间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它们的总和最小。解决方案很明显：

1. 对于A = 2 * B=>B次1和-1.

2. 对于A = 2 * B + 1=> B + 1times1和Btimes -1。