网易校招题之丰收

题目描述

又到了丰收的季节,恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛。
在果园里有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
二分法
#include<bits/stdc++.h>
using namespace std;
int binarySearch(vector<int>&a, int target)
{
	int low = 0, high = a.size() - 1;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (a[mid] == target)
		{
			return mid;
		}
		else if (a[mid] < target)
		{
			low = mid + 1;
		}
		else
			high = mid - 1;
	}
	return low;//注意,要大于target

}
int main() {
	int n;
	cin >> n;
	vector<int>apple_sum(n + 1, 0);//第i堆的上界
	for (int i = 1; i <= n; ++i) {
		int temp;
		cin >> temp;
		apple_sum[i] = apple_sum[i - 1] + temp;
	}
	int m, q;
	cin >> m;
	for (int i = 0; i != m; ++i) {
		cin >> q;
		cout << binarySearch(apple_sum, q) << endl;//二分找到等于q的数的下标(如果有)
        //或第一个大于q的数的下标
	}
	return 0;
}
迭代器 lower_bound
从小到大的排序数组中,
lower_bound( begin,end,num):
从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num):
从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

从大到小的排序数组中,重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater<type>() ):
从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<type>() ):
从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<long long> apple;
    int n= 0;
    int i = 0;
    cin>>n;
    cin.ignore();
    while(n)
    {
        int m = 0;
        cin>>m;
        if(apple.size()==0)
        {
            apple.push_back(m);
        }
        else
        {
            apple.push_back(m+apple[i]);
            i++;
        }
        n--;
    }
    int quire = 0;
    cin>> quire;
    vector<long long>::iterator it;
    while(quire)
    {
        int m = 0;
        cin>>m;
        it = lower_bound(apple.begin(),apple.end(),m);//获取迭代器
        int ress = it-apple.begin();//获取迭代器所在的位置
        cout << ress+1<<endl;
        quire--;
    }
   return 0;
}



全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 14:45
bg是二本双一流硕,目标是Java后端开发岗,投暑期实习0大厂面试,只有极少的大厂测开,可能投的晚加上简历太烂加上0实习?求大佬们给个建议
程序员小白条:别去小厂,初创或者外包,尽量去中小,100-499和500-999,专门做互联网产品的,有公司自研的平台和封装的工具等等,去学习一些业务相关的,比如抽奖,积分兑换,SSO认证,风控,零售等等,目标 Java 后端开发吗?你要不考虑直接走大厂测开?如果技术不行的话,有面试你也很难过的
实习,不懂就问
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务