构造大小为 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&nbsp;+&nbsp;a2&nbsp;+&nbsp;...&nbsp;+&nbsp;an)^2&nbsp;=&nbsp;(a1^2&nbsp;+&nbsp;a2^2&nbsp;+&nbsp;...&nbsp;+&nbsp;an^2)&nbsp;+&nbsp;2&nbsp;*&nbsp;(a1a2&nbsp;+&nbsp;a1a3&nbsp;+&nbsp;...&nbsp;+&nbsp;ana(n-1))或者换句话说（这里无法很好地格式化它）：(sum_{i}(ai))^2&nbsp;=&nbsp;sum_{i}(ai^2)&nbsp;+&nbsp;2&nbsp;*&nbsp;sum_{1&nbsp;<=&nbsp;i&nbsp;<&nbsp;j&nbsp;<=&nbsp;N}(ai&nbsp;*&nbsp;aj)我们在这里寻找sum_{1 <= i < j <= N}(ai * aj).经过一些简单的添加，我们得到：sum_{1&nbsp;<=&nbsp;i&nbsp;<&nbsp;j&nbsp;<=&nbsp;N}(ai&nbsp;*&nbsp;aj)&nbsp;=&nbsp;1&nbsp;/&nbsp;2&nbsp;*&nbsp;((sum_{i}(ai))^2&nbsp;-&nbsp;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&nbsp;<=&nbsp;i&nbsp;<&nbsp;j&nbsp;<=&nbsp;N}(ai&nbsp;*&nbsp;aj)&nbsp;=&nbsp;1&nbsp;/&nbsp;2&nbsp;*&nbsp;((sum_{i}(ai))^2&nbsp;-&nbsp;sum_{i}(ai^2))&nbsp;=&nbsp;1&nbsp;/&nbsp;2&nbsp;*&nbsp;((sum_{i}(ai))^2&nbsp;-&nbsp;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=>&nbsp;B + 1times1和Btimes&nbsp;-1。