思路
通过动态规划计算出所有连续子序列的力量值之和,并将其存储在一个数组中然后排序,遍历一遍数组,找到相邻两个力量值之和的差的绝对值的最小值,然后输出这个答案就行了。
时间复杂度大概是 \(O(n^2 \log n)\)。
来个 python 的代码
def min_power_diff(n, a):# 计算所有连续子序列的力量值之和
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i - 1] + a[i - 1]
# 计算差值并排序
diffs = []
for i in range(1, n + 1):
for j in range(i, n + 1):
diff = abs(prefix_sum[j] - prefix_sum[i - 1])
diffs.append(diff)
diffs.sort()
# 找到相邻两个力量值之和的差的最小值
min_diff = float('inf')
for i in range(1, len(diffs)):
min_diff = min(min_diff, diffs[i] - diffs[i - 1])
return min_diff
n = int(input())
a = list(map(int, input().split()))
# 输出答案
result = min_power_diff(n, a)
print(result)
标签:P10429,diffs,min,题解,sum,range,蓝桥,prefix,diff
From: https://www.cnblogs.com/BadBadBad/p/18180225/P10429