数学 范围分析及组合

题目

重述

略

思路

1.对范围的数字敏感度

我们发现，虽然n的范围比较大，但是a_i可选取范围较小。也就意味着，可能会出现多组重复计算的情况。

所以应对的情况就是，把所有的组合都算出来（1000*1000种可能，时间复杂度是可以接受的）

2.简化组合配对

如果仅仅考虑到上述情况并进行计算，最后的结果还是会超时。这里呢还有一个结论

python

m = list(map(int, input().split()))
a = [[0 for i in range(0, 1001)] for j in range(0, 1001)]
for i in range(0, 1001):
    for j in range(i, 1001):
        a[i][j] = abs(i + j - 1000)
        a[j][i] = abs(i + j - 1000)
s = 0
for i in range(0, n):
    for j in range(i, n):
        s = s + a[m[i]][m[j]]
print(s)

如图在配对阶段，仍然使用暴力的方法，最终是超时了的。所以在这里，我们还需要直接对重复出现的可能性进行直接的计算。

这里需要注意的一点是，虽然说我们的累加次序是从j= i - n， 但是由于他的两个算法都是加法，所以其实哪个在前哪个在后区别不是很大。因此，某个函数f(i, j)被使用到的概率，是 i 出现的次数 * j 出现的次数。

最后注意一下python输出....牛客要求输出整数...

题解

python

m = list(map(int, input().split()))
a = [[0 for i in range(0, 1001)] for j in range(0, 1001)]
b = [0 for i in range(0, 1001)]
for i in range(0, 1001):
    for j in range(i, 1001):
        a[i][j] = abs(i + j - 1000)
        a[j][i] = abs(i + j - 1000)
s = 0
for i in m:
    b[i] = b[i] + 1
for i in range(1001):
    for j in range(i, 1001):
        if i != j:
            s = s + a[i][j] * b[i] * b[j]
        else:
            s = s + (b[i]+1)*b[i]/2 * a[i][j]
print(int(s))