丰收

题目难度：二星
考察点：前缀和、二分

方法1：暴力算法

1. 分析：
   对于的每个询问x，我们从1到n遍历整个数组，期间计算加和sum，直到在第i堆苹果满足x>=sum的时候,此时x属于第i堆苹果，输出即可。

算法实现：
(0). 输入每堆对应的苹果数，用数组记录一下。
(1). 对于查询的x，从第1堆开始遍历，sum表示前i堆的苹果数之和，如果sum>=x,就输出i（属于第i堆）

2. 复杂度分析：
   时间复杂度：O(n^2)
   空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   const int MAXN = 1e5+5;
   int a[MAXN];
   int main() {
    int n; cin>>n;
    for(int i=0; i<n; i++) cin>>a[i];
    int m; cin>>m;
    while(m--) {
        int x; cin>>x;
        int sum = 0;
        for(int i=0; i<n; i++) {
            sum += a[i];
            if(sum >= x) {
                cout<<i+1<<endl;
                break;
            }
        }
    }
    return 0;
   }

方法2：前缀和+二分算法

1. 分析：
   根据之前的算法我们进行优化，分析一下究竟是什么导致了时间复杂度这么高呢？由于我们在m次询问中多次重复计算了从1-i的加和，那么我们可以想办法用一个前缀和数组预处理一下i-i区间的加和，例如:sum[i]表示区间[1,i]的所有苹果的个数和。然后对于查询x来说，我们只需要从sum数组中找到第一个大于等于x的值的下标，输出下标即可，这个显然就可以用二分来做了。
   tips：a. 因为所有数都是正整数，那么sum数组一定是递增的（即有序的）
   b. 二分可以采用系统自带的lower_bound函数。

算法实现：
(0). 输入每堆对应的苹果数，用sum数组记录一下前缀和。
(1). 对于查询x来说，二分sum数组找到第一个大于等于x的下标，输出即可。
2. 复杂度分析：
时间复杂度：O(m*log(n))
空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   const int MAXN = 1e5+5;
   int sum[MAXN];
   int main() {
    int n; cin>>n;
    for(int i=1; i<=n; i++) {
        int x; cin>>x;
        sum[i] = sum[i-1] + x;
    }
    int m; cin>>m;
    while(m--) {
        int x; cin>>x;
        int id = lower_bound(sum+1, sum+n+1, x)-sum;
        cout<<id<<endl;
    }
    return 0;
   }