这是我遇到的一个问题：
给出了两个整数：N（数组的大小）和S（数组的所有元素的必需总和）
要求以以下方式构造大小为N及其元素之和的数组：
数组包含N个正非零值
向量的元素是不同的
数组中最大和最小元素之间的绝对差很小
如果此绝对差相等的解多于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且总和<= S的N个连续数字。
因此，让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
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句