网易校招题之丰收

题目描述

又到了丰收的季节，恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌，小易不太相信，所以他想考考牛牛。
在果园里有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

输入

输出

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;
}