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

Question

我正在尝试 Bonetrousle HackerRank challenge.

问题如下:

找到 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 递增，直到达到总和。我修改了代码，为每个元素分配最大可能值，然后在它打破约束时递减它，但显然它没有太大帮助。

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

Answer 1

首先，找到总和<= N 的B 最大连续 个整数。如果此序列以 < 1 的整数开始或以 > K

的整数结束，则该问题是不可能的

从x开始的B整数之和是B*(2x+B-1)/2，所以只要求解< strong>x 直接。

显然，如果您要为从 x 开始的序列中的每个整数加一，那么您将得到下一个 B 个连续的整数，它们的和是 > N，所以你不需要递增那么多。只需将序列中最高的 N-sum 整数加 1 即可得出正确的总和。