python - 优化问题中蛮力数的算法

Question

有多少对(i, j)存在这样1 <= i <= j <= n, j - i <= a？ 'n'并'a'输入数字。

问题是我的算法在增加“n”或“a”时太慢了。
我想不出一个正确的算法。
执行时间必须小于 10 秒。

测试：

• n = 3
  a = 1
  对数 = 5

• n = 5
  a = 4
  对数 = 15

• n = 10
  a = 5
  对数 = 45

• n = 100
  a = 0
  对数 = 100

• n = 1000000
  a = 333333
  对数 = 277778388889

• n = 100000
  a = 555555
  对数 = 5000050000

• n = 1000000
  a = 1000000
  对数 = 500000500000

• n = 998999
  a = 400000
  对数 = 319600398999

• n = 898982
  a = 40000
  对数 = 35160158982

n, a = input().split()

i = 1
j = 1

answer = 0

while True:
    if n >= j:
        if a >= (j-i):
            answer += 1

            j += 1

        else:
            i += 1
            j = i

            if j > n:
                break

    else:
        i += 1
        j = i

        if j > n:
            break

print(answer)

标签： pythonalgorithm

Answer 1

您正在使用二次算法，但您应该能够将其变为线性（甚至可能更好）。

主要问题是确定有多少对，给定i和j。将其拆分为一个函数是很自然的。

一个关键点是，对于i固定的，j与之相配i的在 到 的范围i内min(n,i+a)。这是因为j-i <= a等价于j <= i+a。

对于min(n,i+a) - i + 1给j定的i. 这将导致：

def count_pairs(n,a):
    return sum(min(n,i+a) - i + 1 for i in range(1,n+1))

count_pairs(898982,40000)35160158982在大约一秒钟内评估为。如果这仍然很慢，请进行更多的数学分析。