首页 > 试题广场 >

丰收

[编程题]丰收
  • 热度指数：34799 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
又到了丰收的季节，恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌，小易不太相信，所以他想考考牛牛。
在果园里有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
算法知识视频讲解
开通博客
头像 c小白进击之路
发表于 2021-04-11 11:55:14
每个苹果编号1到n； 第二堆苹果的虚拟总数量是前面的和；     for(int i=1;i<=n;i++){         scanf("%d",&sz[i]);  &nb 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 白色高跟鞋
发表于 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 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Ⅲ_Dc
发表于 2022-03-07 14:15:32
">#include<vector> using namespace std; int main(void) { int n; cin>>n; vector<int> a(n+1,0); a[0] = 0; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 laglangyue
发表于 2020-05-18 20:36:19
相比二分更优，二分法每个询问都要进行一次二分查找，通过对询问数组排序可以直接规避掉查找。思路：排序，前缀和+排序(复杂度都在排序上)对苹果堆数组进行前缀和计算(在输入时直接计算)，对询问数组排序。为了保证输出，利用hashmap映射一下数组与结果。 package org.niuke.solut 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 牛客题解官
发表于 2020-06-04 14:31:16
题目难度：二星考察点：前缀和、二分 方法1：暴力算法 分析：对于的每个询问x，我们从1到n遍历整个数组，期间计算加和sum，直到在第i堆苹果满足x>=sum的时候,此时x属于第i堆苹果，输出即可。 算法实现：(0). 输入每堆对应的苹果数，用数组记录一下。(1). 对于查询的x，从第1堆开 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 网易 算法工程师 PHP工程师 2019 查找 Java工程师
来自：网易2019秋季校园招...
上传者：小小
难度：
122条回答 22105浏览

热门推荐

通过挑战的用户

查看代码

相关试题

丰收

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号