代码之家  ›  专栏  ›  技术社区  ›  randomAlgo

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

  •  -1
  • randomAlgo  · 技术社区  · 10 月前

    我正在进行以下任务:

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

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

    约束条件 :N,Q<=10 6. ,x <=10 9

    输入 : 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. .

    1 回复  |  直到 10 月前
        1
  •  2
  •   Matt Timmermans    10 月前

    起始长度为x、目标长度为v的弹簧的总作用力与(x-v)成正比 2. .

    对于一堆N个弹簧,求和[(x v 2. ]=总和[x 2. ]-2v*总和[x ]+Nv 2.

    请注意,求和根本不依赖于目标长度,因此您可以预先计算Sum[x 2. ]和总和[x ]O(n)时间内数组的所有前缀。

    然后,对于每个查询,您可以查找适当的总和,并计算O(1)时间内任何v的最小成本,总共给出O(n+q)。

    正如您已经确定的那样,最小努力目标长度是平均弹簧长度Sum[x ]/N.这并不总是一个整数,所以只需尝试它两边的2个整数。