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

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个正值{1,2,3...N)之和为(N + 1)*N/2

因此，我们可以轻松得出 N 个连续正数(从 a 开始)求和的公式

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

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

所以让 dif = S - (N + 2*a - 1)*N/2 -> 所以最后的 dif 数字应该加上 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     
}