将弹簧设置为相同长度的成本最低

我正在进行以下任务:

您将收到一组经过排序的弹簧。它们中的每一个都是在特定的维度上生产的,每次拉伸或压缩都需要相当大的努力。 将尚未移动一厘米的弹簧加长或缩短需要1个单位的努力。同一弹簧的每次连续拉伸或压缩都需要额外的1个单位的力。更确切地说,如果你想把弹簧延长D厘米,他会连续付出1,2,D个单位的努力。

你的任务是回答q个关于将k最短弹簧设置为相同长度所需的最小工作量的问题。

约束条件 :N,Q<=10 ^6. ,x _我 <=10 ⁹

输入 : N、 Q
x _1. ,x _2. ,x _3. , ...
q _1. q _2. q _3. , ...

N-弹簧数量
x _我 -第i个弹簧的长度(注意x _我 <=x _i+1 )
q _我 -在第i个问题中,应该将多少个弹簧设置为相同的长度

输出 : 问题的答案-将k最短弹簧设置为相同长度所需的最小努力。因为答案可能很大,所以按10^9+7的模打印。

我的解决方案尝试 : 我发现,当弹簧设置为弹簧的平均长度时,可以实现最小的努力。然而,在这种方法中,算法的复杂度为O(n*q),对于给定的约束来说太慢了。

我怎样才能更快地解决这个问题?

在我的残酷方法中,我计算弹簧的平均长度,然后线性计算每个弹簧的成本。这对N来说太慢了,Q<=10 ^6. 但对于n来说就足够了,q<=10 ^3. .