如何快速和数组中给定范围内的元素？

Question

我很难解决这个问题：

第一线输入- N. N+1是火车站的数目.

第二行输入-N个整数c( i ) -在站i-1和i之间的票价。

第三条输入线-k-乘客数。

下一条k线: int a和int b(每个乘客的第一站也是最后一站)。

期望输出:每个客户的机票价格。也就是。

输入：

4
12 23 34 45
3
0 4
1 3
3 2

输出：

114
57
34

我的代码：

n = int(input())                                                                
prices = list(map(int, input().split()))                                        
x = int(input())                                                                

for i in range(x):                                                              
    a, b = sorted(map(int, input().split()))                                    
    print(sum(prices[a:b]))    

我想我的解决方案远远不是最优的，因为我得到了Time Limit Exceeded错误。

Answer 1

使用累积数组的解决方案

def accum(a):
    " creates the accumulation of array a as input "
    b = [0] * (len(a) + 1)
    for i, v in enumerate(a):
      b[i+1] = b[i] + v

    return b

def price(acc, t):
  " Price using accumulated array "
  # t provides the start, stop points (e.g. [0, 4])
  mini, maxi = min(t), max(t)
  return acc[maxi] - acc[mini]

对上述函数的使用

prices = [12, 23, 34, 45]

# create assumulation of prices
acc = accum(prices)

# Using your test cases
tests = [[0, 4], [1, 3], [3, 2]]
for t in tests:
  print(t, price(acc, t))

输出

[0, 4] 114
[1, 3] 57
[3, 2] 34