描述

牛牛有一个苹果园。又到了一年一度的收获季，牛牛现在要去采摘苹果买给市场的摊贩们。

牛牛的果园里面有n棵苹果树，第i棵苹果树上有a_{i}ai个果子。
牛牛为了保证果子的新鲜程度，每天都会去苹果树上采摘果子。
牛牛特意安排一个计划表：

  • 计划m天去采摘果子。
  • 对于第i天，它会去所有果树上轮流采摘b_{i}bi个果子。
  • 如果对于第i天，某棵果树上没有b_{i}bi个果子，那么它只会把当前果树上的果子采摘完。
牛牛想知道它每天能供应多少个苹果给市场的摊贩们。

返回一个数组 （代表每一天的真实苹果采摘量）

示例1

输入： 
[10,20,10],[5,7,2]
复制
返回值： 
[15,17,2]
复制
说明： 
苹果树上的果子变化[10,20,10]-->[5,15,5]-->[0,8,0]-->[0,6,0]

备注： 

		

			一个vector a (1 \leq a_{i}\leq 10^{9}1≤ai≤109)
一个vector b (1 \leq b_{i} \leq 10^{9}1≤bi≤109)
		


		

			n=a.size(); m=b.size() ;1 \leq n,m \leq 10^{5}n=a.size();m=b.size();1≤n,m≤105

题目分析：
1、使用暴力搜索法：使用两层for循环，外层轮询b数组，内层轮询a数组，即计算当每天采摘b[i]个果子时，果树上的a[j]个果子够不够采摘，
够的话sum+=b[j]；不够的话sum加实际上剩余的全部个数。暴力遍历统计的方法运行起来会超时！！
2、对暴力遍历方法进行优化，可以将a数组进行排序，即对于果树从果树小的数开始遍历。
使用类似前缀和的方式，循环遍历b数组，到第i天每棵树总共需要采摘的苹果数量记为pre，
使用pre与a[j]数组进行比较，若a[j] < pre，则说明第j棵树不够第i天采摘，把剩余的摘完即可；剩下足以采摘的树直接用乘法计算、不用再轮询。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型vector
     */
     //会超时
    /*vector<long> solve(vector<int>& a, vector<int>& b) {
        vector<long> res;
        // write code here
        for (int i = 0; i < b.size(); i++) {
            long sum = 0;
            for (int j = 0; j < a.size(); j++) {
                if (a[j] == 0) continue;
                if (a[j] >= b[i]) {
                    sum += b[i];
                    a[j] = a[j] - b[i];
                } else {
                    sum += a[j];
                    a[j] = 0;
                }
            }
            res.push_back(sum);
        }
        return res;
    }*/
     vector<long> solve(vector<int>& a, vector<int>& b) {
        vector<long> res;
        // write code here
        int n = a.size();
        int m = b.size();
        long pre = 0;
        sort(a.begin(), a.end());
        for (int i = 0, j = 0; i < m; i++) {
            
            long sum = 0;
            pre += b[i];
            while (j < n && a[j] < pre) {
                sum = sum + (b[i] - (pre - a[j]));
                j++;
            }
            sum += ((n - j) * b[i]);
            res.push_back(sum);
        }
        return res;
    }
};