網易筆試題：豐收（python解答，bisect）

題目描述

又到了豐收的季節，恰逢小易去牛牛的果園裡遊玩。

牛牛常說他對整個果園的每個地方都了如指掌，小易不太相信，是以他想考考牛牛。

在果園裡有N堆蘋果，每堆蘋果的數量為ai，小易希望知道從左往右數第x個蘋果是屬于哪一堆的。

牛牛覺得這個問題太簡單，是以希望你來替他回答。

輸入描述:

第一行一個數n(1 <= n <= 105)。
第二行n個數ai(1 <= ai <= 1000)，表示從左往右數第i堆有多少蘋果
第三行一個數m(1 <= m <= 105)，表示有m次詢問。
第四行m個數qi，表示小易希望知道第qi個蘋果屬于哪一堆。
           

輸出描述:

m行，第i行輸出第qi個蘋果屬于哪一堆。
           

示例1

輸入

5
2 7 3 4 9
3
1 25 11
           

輸出

1
5
3
           

python答案

from bisect import bisect_left
n = int(input())
a = list(map(lambda x:int(x),list(input().split(' '))))
m = int(input())
q = list(map(lambda x:int(x),list(input().split(' '))))
for i in range(1,len(a)):
    a[i] += a[i-1]
for i in q:
    print(bisect_left(a,i)+1)
           

這題思路不難，隻不過不用二分查找的話會逾時，Python 有一個 bisect 子產品，用于維護有序清單。bisect 子產品實作了二分法用于插入元素到有序清單。那麼bisect_left方法會傳回要被插入元素的索引，若該元素已存在那麼傳回該元素左邊的索引。