牛客网真题2019-11-丰收

相比二分更优，二分法每个询问都要进行一次二分查找，通过对询问数组排序可以直接规避掉查找。
思路：排序，前缀和+排序(复杂度都在排序上)
对苹果堆数组进行前缀和计算(在输入时直接计算)，对询问数组排序。为了保证输出，利用hashmap映射一下数组与结果。

package org.niuke.solution11;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] apple = new int[n];
        int temp = 0;
        for(int i = 0; i < n; i++){
            temp += sc.nextInt();
            apple[i] = temp;
        }
        int m = sc.nextInt();
        int[] req = new int[m];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < m; i++){
            req[i] = sc.nextInt();
        }
        int[] reqCopy = Arrays.copyOf(req, m);
        Arrays.sort(req);
        int index = 0;
        for(int i = 0; i < m; i++){
            while (index < n)
                if(req[i] <= apple[index]){
                    map.put(req[i], index + 1);
                    break;
                }else{
                    index++;
                }
        }
        for(int i = 0; i < m; i++){
            System.out.println(map.get(reqCopy[i]));
        }
    }
}