动态规划 - 固定大小数组的固定总和

Question

这里有一个问题困扰着我：

Two integers are given: N (the size of the array) and S (the required sum of all elements of the array)

The requirements are to construct an array of size N and with the sum of its elements S in such a way that:

• The array is to contain N positive non-zero values

• The elements of the vector are distinct

• The absolute difference between the largest and smallest element in the array is minimal

• If there are more than 1 solutions in which this absolute difference is equal, the minim-lexicographic solution will be shown.

我真的不知道如何开始这个问题。任何帮助都会很可爱。

Answer 1

我认为可以通过构造来实现。

取 N = 6 和 S = 30

1) 像这样初始化你的数组：{1,2,3,4,5,6}

2）从最新到第一个循环递增：

{1,2,3,4,5,6} S = 21
{1,2,3,4,5,7} S = 22
{1,2,3,4,6,7} S = 23
{1,2,3,5,6,7} S = 24
{1,2,4,5,6,7} S = 25
{1,3,4,5,6,7} S = 26
{2,3,4,5,6,7} S = 27

再次循环：

{2,3,4,5,6,7} S = 27
{2,3,4,5,6,8} S = 28
{2,3,4,5,7,8} S = 29
{2,3,4,6,7,8} S = 30

也许有一个公式可以找到一个好的开始。例如，您可以开始于：

 {S/N - N, S/N - N+1, S/N - N+2, ...}

Answer 2

前N个正值{1,2,3...N)之和为(N + 1)*N/2

所以，我们很容易得出一个N个连续正数（从a开始）求和的公式

((N + a - 1) + a)*N/2 = (N + 2*a - 1)*N/2

使用二分查找，我们可以找到最大起始数a[=31=的N个连续数] 总和 <= S.

所以让 dif = S - (N + 2*a - 1)*N/2 -> 所以最后的差异数字应该加上 1 其余的 N - dif 数字是 N - dif + a, ..., a 。

伪代码

int start = 1;
int end = S;
int result = 1;
while(start <= end){
    int mid = (start + end)/2;
    int sum = sum(mid);   
    if(sum <= S){
       result = max(mid,result); 
       start = mid + 1;
    }else{
       end = mid - 1;
    } 
}
//So we know that the sequence starting at result
//Now we need to find the diff
int dif = S - sum(result);

for(int i = 0; i < N; i++){
   if(i >= N - dif ){//last N - dif number is added one
      print (i + result + 1);

   }else{
      print (i + result);
   }
}

int sum(int a){//Return sum from a to N + a - 1
    return (N +2*a - 1)*N/2     
}