我要招人

去企业版

首页 > 试题广场 >

苹果树

[编程题]苹果树

热度指数：2018 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

计划m天去采摘果子。
对于第i天，它会去所有果树上轮流采摘 $b_{i}$ 个果子。
如果对于第i天，某棵果树上没有 $b_{i}$ 个果子，那么它只会把当前果树上的果子采摘完。

牛牛想知道它每天能供应多少个苹果给市场的摊贩们。

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

示例1

输入

[10,20,10],[5,7,2]

输出

[15,17,2]

说明

苹果树上的果子变化[10,20,10]-->[5,15,5]-->[0,8,0]-->[0,6,0]

备注:

一个vector a ()
一个vector b ()

算法知识视频讲解

0x105

#include<bits/stdc++.h>
class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        // write code here
        //将苹果树按果子数量排序
        sort(a.begin(), a.end());
        int n = b.size();
        vector<long> res(n, 0);
        //利用前缀和，优化掉摘果子过程
        vector<long> c(n+1, 0);
        c[0] = 0;
        for(int i = 1; i <= n; i++) {
            c[i] = b[i-1] + c[i-1];
        }
        //l代表第一个还有苹果的苹果树下标
        int l = 0;
        //遍历天数
        for(int i = 1; i <= n; i++) {
            //如果当前要摘苹果的小于l还剩的苹果数量
            if(c[i] < a[l]) {
                res[i-1] = (n - l) * (c[i]-c[i-1]);
            } else {
            //否则不断把苹果摘空直到出现剩余果子大于b[i](即c[i]-c[i-1])的树
                while(l < n && a[l] <= c[i]) {
                    res[i-1] += (a[l]-c[i-1]);
                    l++;
                }
                //剩下的树直接用乘法得到答案
                res[i-1] += (n-l) * (c[i]-c[i-1]);
            }
        }
        return res;
    }
};

发表于 2020-07-16 11:07:01 回复(0)

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型vector
     */
    vector<long> solve(vector<int>& a, vector<int>& b) {
        int n = a.size(), m = b.size();
        sort(a.begin(), a.end());
        vector<long> r(m);
        long s = 0;
        for(int i=0,j=0;i<m;i++){
            s += b[i];
            r[i] = (n-j)*b[i];
            while(j<n && a[j]<s)
                r[i] -= s-a[j++];
        }
        return r;
    }
};

发表于 2020-08-03 18:19:23 回复(0)

C/C++

刘禅挥泪斩孔明

class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());
        int n(a.size()), m(b.size());
        vector<long> ans(m);
        long s = 0;
        for (int i = 0, j = 0; i < m; i++) {
            s += b[i];
            ans[i] = long(n-j) * b[i];
            while (j < n && a[j] < s) ans[i] -= s - a[j++];
        }
        return ans;
    }
};

发表于 2020-04-02 21:17:04 回复(0)

科大15届软工代言人

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型一维数组
     */
    int index = 0;
    public long[] solve (int[] a, int[] b) {
        long[] result = new long[b.length];
        long subtract = 0;
        for(int i = 0; i < a.length; i++) {
            heapInsert(a, a[i]);
        }
        for(int i = 0; i < b.length; i++) {
            subtract += b[i];
            long sum = b[i] * index;
            int j = 0;
            while(j < index && a[j] < subtract) {
                sum -= subtract - a[j];
                heaplify(a);
            }
            result[i] = sum;
        }
        return result;
    }
    public void heaplify(int[] heap) {
        if(index == 1) {
            heap[0] = 0;
        }
        heap[0] = heap[index - 1];
        index--;
        int cur = 0;
        while(cur < index) {
            int leftChild = cur * 2 + 1;
            int rightChild = cur * 2 + 2;
            int smallest = cur;
            if(leftChild < index && heap[leftChild] < heap[cur]) {
                smallest = leftChild;
            }
            if(rightChild < index && heap[rightChild] < heap[smallest]) {
                smallest = rightChild;
            }
            if(smallest == cur) {
                break;
            }else {
                int temp = heap[cur];
                heap[cur] = heap[smallest];
                heap[smallest] = temp;
                cur = smallest;
            }
        }
    }
    public void heapInsert(int[] heap, int value) {
        if(index == 0) {
            heap[0] = value;
            index++;
            return; 
        }
        heap[index++] = value;
        int cur = index - 1;
        while(cur > 0) {
            int parent = (cur - 1)/2;
            if(heap[cur] < heap[parent]) {
                int temp = heap[parent];
                heap[parent] = heap[cur];
                heap[cur] = temp;
                cur = parent;
            }else {
                break;
            }
        }
    }
}

发表于 2021-07-04 10:30:13 回复(0)

Java

Salieri111

public class Solution {
/**
*
* @param a int整型一维数组
* @param b int整型一维数组
* @return long长整型一维数组
*/
public long[] solve (int[] a, int[] b) {
// write code here
Queue<Integer> heap = new PriorityQueue<>();
for(int i:a){
heap.add(i);
}
long[] ans = new long[b.length];
int mark = 0;
for(int i = 0; i < b.length; i++){
mark += b[i];
ans[i] =(long) b[i]*heap.size();
while(!heap.isEmpty() && mark>=heap.peek()){
ans[i] -= (mark-heap.poll());
}
}
return ans;
}
}

发表于 2020-08-03 10:54:19 回复(0)

沙滩上捡贝壳

class Solution:
    def solve(self , a, b):
        a.sort()
        n = len(a)
        res = []
        tol_to_take = 0
        last_idx = 0
        for cur_to_take in b:
            tol_to_take += cur_to_take
            to_take_today = 0
            while last_idx < n and tol_to_take >= a[last_idx]:
                to_take_today += (a[last_idx] - tol_to_take + cur_to_take)
                last_idx += 1
            to_take_today += (n - last_idx) * cur_to_take
            res.append(to_take_today)
        return res

发表于 2020-07-21 20:24:50 回复(0)

Java

我只是个小菜鸡啊

大佬们，哪里不对，只能通过 70%。。。

public long[] solve (int[] a, int[] b) {
    PriorityQueue heap = new PriorityQueue();
    for (int i : a) {
        heap.add((long) i);
    }
    long[] result = new long[b.length];
    long count = 0;
    for (int i = 0; i < b.length; i++) {
        count += b[i];
        while (!heap.isEmpty() && heap.peek() <= count) {
            result[i] += (heap.poll() - (count - b[i]));
        }
        result[i] += heap.size() * b[i];
    }
    return result;
}

发表于 2020-07-03 17:58:17 回复(1)