时间戳

首页 > 解决方案 > 骨肉 | 在 K 之下找到 B 个不同的正整数，使得它们的和为 N，或者说这是不可能的。| 超时错误

algorithm - 骨肉 | 在 K 之下找到 B 个不同的正整数，使得它们的和为 N，或者说这是不可能的。| 超时错误

问题描述

我正在尝试Bonerousle HackerRank 挑战。

问题如下：

在 K 之下找到 B 个不同的正整数，使得它们的和为 N，或者说这是不可能的。

约束：

n, k <= 10^18
b <= 10^5

如果给定的 N 位于最小值（取前 B 个元素）和最大值（取最后 B 个元素）可能的总和之间，您可以检查是否存在解决方案。从那里开始，我从最小总和开始，并尝试通过为每个元素分配最大可能值而不破坏约束来使其达到 N。（无重复，总和 == N）

下面是我写的代码。

def foo1(n,k,b):
    minSum = (b*(b+1))//2
    maxSum = (b)*(k-b+1+k)//2
    #maxSum = (k*(k+1))//2 - minSum
    #print(minSum, maxSum)


    if n>=minSum and n<=maxSum:
        minArr = [i for i in range(1,b+1)]
        minArr.reverse()
        sumA = sum(minArr)

        maxA = k
        for i in range(len(minArr)):
            tmp = minArr[i]
            minArr[i] = maxA
            sumA = sumA-tmp+minArr[i]

            while sumA > n:
                sumA -=1
                minArr[i] -= 1
            maxA = minArr[i]-1
            """
            while sumA+1 <= n and minArr[i]+1 <= k and minArr[i]+1 != maxA:
                #print(minArr, maxA)

                minArr[i]+=1
                sumA +=1
            maxA = minArr[i]    
            if sumA == n:
                break
            """

    else:
        return [-1]
    return minArr

该代码输出正确的解决方案，但它在 4 个测试用例的黑客排名中超时。（样本 n,b,k : 19999651, 20000000, 6324）对于相同的测试用例，它会在我的机器上 3 秒内给出答案。

最初我认为问题出在注释代码上，因为我试图将每个元素数组 1×1 递增，直到达到总和。我修改了代码，为每个元素分配了最大可能值，然后如果它违反了约束，则将其递减，但显然它并没有太大帮助。

关于修改代码以使其通过时序约束或更快的算法的任何建议？

标签： algorithm

解决方案

首先，找到sum <= N的B个最大连续整数。如果此序列以整数 < 1 开始或以整数 > K结束，则问题是不可能的

从x开始的B个整数之和为B*(2x+B-1)/2，所以直接求解x即可。

显然，如果您要对从x开始的序列中的每个整数加一，那么您将获得下一个 B个连续整数，并且它们的总和 > N，因此您不需要增加那么多。只需将 1 加到序列中最高的N-sum整数即可使总和正确。

推荐阅读