首页 > 试题广场 >

丰收

[编程题]丰收

热度指数：34755 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

又到了丰收的季节，恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌，小易不太相信，所以他想考考牛牛。
在果园里有N堆苹果，每堆苹果的数量为a_i，小易希望知道从左往右数第x个苹果是属于哪一堆的。
牛牛觉得这个问题太简单，所以希望你来替他回答。

输入描述:

第一行一个数n(1 <= n <= 10⁵)。
第二行n个数a_i(1 <= a_i<= 1000)，表示从左往右数第i堆有多少苹果
第三行一个数m(1 <= m <= 10⁵)，表示有m次询问。
第四行m个数q_i，表示小易希望知道第q_i个苹果属于哪一堆。

输出描述:

m行，第i行输出第q_i个苹果属于哪一堆。

示例1

输入

输出

1
5
3

算法知识视频讲解

Python

啦啦啦jk

importsys

importbisect

inp=sys.stdin.readlines()

n=int(inp[0].strip())

a=list(map(int, inp[1].strip().split()))

m=int(inp[2].strip())

q=list(map(int, inp[3].strip().split()))

number=[]

cout=0

foriinrange(n):

cout=cout+a[i]

number.append(cout)

foriinrange(m):

num=bisect.bisect(number,q[i]-1)

print(num+1)

发表于 2020-03-28 19:54:29 回复(0)

Python

外包不准吃公司零食

import sys
import bisect
while True:
    line = sys.stdin.readline()
    if not line:
        break
    n = int(line)
    A = list(map(int, sys.stdin.readline().split()))
    m = int(sys.stdin.readline())
    Q = list(map(int, sys.stdin.readline().split()))
    sum1 = 0
    for i in range(n):
        sum1 += A[i]
        A[i] = sum1
    for q in Q:
        index = bisect.bisect(A,q-0.5) # 如果q等于A里面的某个元素会被插到后面，所以减一下
        print(index+1)

先列每一溜的累加值，然后用bisect神器插值求解 ->_->

发表于 2020-02-13 12:18:26 回复(0)

Python

ZC_0_0

考虑到每次都重新搜索会比较费时，所以把待求解的数据排序，然后结果依次放在字典里，最后查找字典输出结果：

n=int(input())

ai=list(map(int,input().split()))
m=int(input())
qi=list(map(int,input().split()))

qi_sorted=sorted(qi)
ai_sum=[0 for i in range(n)]
ai_sum[0]=ai[0]
for i in range(1,n):
ai_sum[i]=ai_sum[i-1]+ai[i]

temp=0
director={}
for i in qi_sorted:
while i > ai_sum[temp]:
temp+=1
director[i] =1+temp

for i in qi:
print(director[i])

发表于 2019-10-04 15:40:06 回复(0)

Python

乘号痕😶

def bisect_left(data, key):
    if not data:
        raise ValueError('Invail Input')
    low, high = 0, len(data) - 1
    while low < high:
        mid = (low + high) // 2
        if key > data[mid]: low = mid + 1
        else: high = mid
    return low


n = int(input())
data = list(map(int, input().split()))
q = int(input())
query = list(map(int, input().split()))
max_count = [0] * (n + 1)
for i in range(1, n + 1):
    max_count[i] = max_count[i-1] + data[i-1]
for i in query:
    print(bisect_left(max_count, i))

二分查找

发表于 2019-09-14 17:13:37 回复(0)

Python

国企程序锅

# 二分查找
def BST(a,left,right,target):
    while(left<=right):
        mid = left + (right - left)//2
        if a[mid] > target:
            right = mid
        if a[mid] < target:
            left = mid
        if a[mid] == target:
            return mid
        if right == left + 1:
            return right

while True:
    try:
        n = int(input())
        a = list(map(int,input().strip().split(' ')))
        m = int(input())
        q = list(map(int,input().strip().split(' ')))
        temp = 0
        new_a = [0]
        for i in a:
            temp =  temp + i
            new_a.append(temp)
        for qq in q:
            print(BST(new_a,0,len(new_a)-1,qq))
    except:
        break

编辑于 2019-08-29 12:14:50 回复(0)

Python

offer一个就好

if __name__=='__main__':
    n=int(input())
    apple=list(map(int,input().strip().split()))
    m=int(input())
    query=list(map(int,input().strip().split()))
    sum=0
    dui = [0]
    for _ in apple:
        sum+=_
        dui.append(sum)#2 9 12 16 25
    for i in query:
        k = 0
        j=n
        while k<=j:
            if i<dui[j]:
                j=j-1
            elif i>dui[k]:
                k+=1
            else:
                break
        print(k)

为什么只通过30%，求大佬帮忙解答

编辑于 2019-08-26 13:25:48 回复(0)

Python

德鲁同学

# python
def fun():
#     n = int(input())
#     A = list(map(int, input().split()))
#     m = int(input())
#     Q = list(map(int, input().split()))
    
    n = 5
    A = [2,7,3,4,9]
    m = 3
    Q = [1,15,11]
    
    
    result = []
    for q in Q:
        temp = 0
        for i in range(n):        
            temp += A[i]
            if temp >= q:
                result.append(i+1)
                break
                
    for r in result:   
        print(r)

编辑于 2019-08-03 10:24:21 回复(0)

Python

临川

#二分法
def binary_search(target,array):
    l = 0
    r = len(array)-1
    while l <= r:
        mid = l + (r-l)//2
        if target > array[mid]:
            l = mid + 1
        elif target < array[mid]:
            r = mid - 1
        else:
            return mid
    return l
n = int(input().strip())
ai = list(map(int,input().strip().split()))
m = int(input())
qi = list(map(int,input().strip().split()))
ans = []
accum = [0]*n
accum[0] = ai[0]
for i in range(1,n):
    accum[i] = accum[i-1]+ai[i]
for ques in range(m):
    print(binary_search(qi[ques],accum)+1)

发表于 2019-07-27 09:16:50 回复(0)

Python

ElonB

"""
构建一个前n项求和的序列，
利用bisect找到应该的插入点
"""
import sys
import bisect

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    m = int(input().strip())
    q = list(map(int, input().strip().split()))
    a_sum = [1]
    for i in range(n):
        a_sum.append(a_sum[-1] + a[i])
    for i in range(m):
        ans = bisect.bisect(a_sum, q[i])
        print(ans)

发表于 2019-07-03 11:34:48 回复(0)

Python

我心声处

# 这四行捕获输入
d_num = int(input())
d = [int(x) for x in input().split()]
query_num = int(input())
query_id = [int(x) for x in input().split()]

# 处理苹果堆列表，第n位上的数据为前n堆苹果的总数
for index in range(1, len(d)):
    d[index] += d[index - 1]
# 显然d现在是一个增序序列，使用标准库bisect中的bisect_left函数即可
# 直接，得到结果。
# 这个函数使用二分查找算法找出在一个有序序列中，保持有序的前提下，
# 插入某一个数可行的插入位置，有相同值时插入到相同值的最左侧。

# 仿标准库中bisect的实现：
def bisect_left(a, needle):
    start = 0  # 起点空位索引
    end = len(a)  # 终点空位索引
    while start < end:
        mid = (start + end) // 2
        if needle > a[mid]:
            # 当needle比a[mid]大时,位点必然出现在mid右侧，
            # 右侧的第一个空位索引为mid + 1,把起点设为mid + 1
            start = mid + 1
        else:  # 如果needle <= a[mid]，位点出现在左侧，
            # 左侧的第一个空位索引为mid,所以终点设为mid
            end = mid
    return start

for apple_id in query_id:
    print(bisect_left(d, apple_id) + 1)

编辑于 2019-05-22 17:41:30 回复(0)

Python

teksab

if __name__ == '__main__':
    count1 = int(input())
     
    count2=input()
    listq = count2.split(' ')
    listq = list(map(int,listq))
     
    query1 = int(input())
     
    count3=input()
    count3=count3.split(' ')
    query_list=list(map(int,count3))
     
    apple_sum=[0 for _ in range(count1)]
    sums=0
    for i in range(count1):
        sums+=listq[i]
        apple_sum[i]=sums
    def BinarySearch1(array,t):
        asc=0
        low = 0
        height =len(array) - 1
        while height>= low: 
            mid =(low + height) // 2  
            if array[mid] >= t:
                asc=mid
                height =mid - 1
            else :
                low =mid + 1
        return asc
    for j in range(query1):
        mid=BinarySearch1(apple_sum,query_list[j])
        print(mid+1)

参考楼上python的，

发表于 2018-09-06 23:49:45 回复(0)

Python

JAson201807292318563

#奇怪了，一直只有百分之20正确率，我这代码是通过不了1000个样本的那个，还是因为超时啊。。。

n = int(raw_input())

num = list(map(int, raw_input().split()))
m = int(raw_input())
ques = list(map(int, raw_input().split()))

for i in range(1,n):
num[i] += num[i-1]

for i in range(m):
for j in range(n):
if ques[i]<num[j]:
print j+1
break

发表于 2018-09-02 00:04:32 回复(1)

Python

ssj

二分法搜索

def main():
n=int(input().strip())
apps=list(map(int,input().strip().split(' ')))
m=int(input().strip())
qs=list(map(int,input().strip().split(' ')))
for i in range(1,n):
apps[i]+=apps[i-1]
for q in qs:
start=0;end=n-1
while start<=end:
mid=(start+end)>>1
if apps[mid]==q:
break
if apps[mid]>q:
end=mid-1
else:
start=mid+1
if apps[mid]>=q:
print(mid+1)
else:
print(mid+2)
if __name__ == '__main__':
main()

编辑于 2018-08-24 14:41:26 回复(0)