首页 > 试题广场 > 丰收
[编程题]丰收
  • 热度指数:31748 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
又到了丰收的季节,恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛
在果园里有N堆苹果,每堆苹果的数量为ai,小易希望知道从左往右数第x个苹果是属于哪一堆的。
牛牛觉得这个问题太简单,所以希望你来替他回答。

输入描述:
第一行一个数n(1 <= n <= 105)。
第二行n个数ai(1 <= a<= 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
头像 豆豆瓣
发表于 2020-04-07 22:59:27
题目难度:二星考察点:前缀和、二分 方法1:暴力算法 分析:对于的每个询问x,我们从1到n遍历整个数组,期间计算加和sum,直到在第i堆苹果满足x>=sum的时候,此时x属于第i堆苹果,输出即可。 算法实现:(0). 输入每堆对应的苹果数,用数组记录一下。(1). 对于查询的x,从第1堆开 展开全文
头像 白色高跟鞋
发表于 2020-04-29 21:05:18
想了两个非暴力的解法:哈希表、前缀+二分查找,写法巧妙的话均能通过。 IO 部分都相同: n = int(input()) a = list(map(int, input().split())) # 左往右数第i堆有多少苹果 m = int(input()) q = list(map(int, i 展开全文
头像 laglangyue
发表于 2020-05-18 20:36:19
相比二分更优,二分法每个询问都要进行一次二分查找,通过对询问数组排序可以直接规避掉查找。思路:排序,前缀和+排序(复杂度都在排序上)对苹果堆数组进行前缀和计算(在输入时直接计算),对询问数组排序。为了保证输出,利用hashmap映射一下数组与结果。 package org.niuke.solut 展开全文