这是我遇到的一个问题:
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.
我真的不知道如何开始这个问题。任何帮助都会很可爱。
最佳答案
前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
}
关于arrays - 动态规划 - 固定大小数组的固定总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28212125/