Find quantiles for a population of N values. These values are index 1, …, N from lowest to highest. 
The Kth Q-quantile of such population is determined by computing the index lk = N * k / Q and 
taking the value found at index lk. 
If lk is not a integer, then it is rounded to the next integer to get the index. 
For a given value of Q, there will be (Q-1) quantiles.

For example, for Q = 2 the 1st (and only) quantile of the population {3, 5, 6} is 5. 
Explanation: N = 3, Q = 2, k = 1, which means l1 = ceiling(3 * 1 / 2) = 2. Value at index 2 is 5.

import java.io.*;
. Waral 鍗氬鏈夋洿澶氭枃绔�,import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);-google 1point3acres
        long Q = scanner.nextInt();
        int M = scanner.nextInt();

        long N = 0;
        Pair[] pairs = new Pair[M];

        for (int i = 0; i < M; i++) {
            int v = scanner.nextInt();
            long c = (long) scanner.nextInt();
            . from: 1point3acres.com/bbs 
            N += c;

            Pair pair = new Pair(v, c);

            pairs[i] = pair;
        }

        // sort the array according to the vi
        Arrays.sort(pairs, new MyPairComparator());

        // Calculate the accmulated count
        for (int i = 1; i < M; i++) {. more info on 1point3acres.com
            pairs[i].count += pairs[i - 1].count;
        }

        // Find all the quantiles 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
        List<Integer> result = findQuantiles(N, Q, pairs);

        for (Integer num : result) {
            System.out.println(num);
        }

        scanner.close();
    }. Waral 鍗氬鏈夋洿澶氭枃绔�,
. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
    public static List<Integer> findQuantiles(long N, long Q, Pair[] pairs) {
        List<Integer> result = new ArrayList<>();.1point3acres缃�

        if (N <= 0 || Q <= 1 || pairs == null || pairs.length == 0) {
            return result;
        }

        // Find the i-th quantile
        for (long i = 1; i < Q; i++) {
            long index = (long) Math.ceil((double) N * i / Q);

            int quantile = binarySearch(pairs, index);
            result.add(quantile);.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
        }

        return result;
    }

    // If it can find the target, return the value with the index of the target
    // Otherwise, return the next value with the index greter than the target
    private static int binarySearch(Pair[] pairs, long target) {
        int lo = 0; 
        int hi = pairs.length - 1;

        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (pairs[mid].count == target) {
                return pairs[mid].value;
            } else if (pairs[mid].count > target) {. from: 1point3acres.com/bbs 
                hi = mid;
            } else {
                lo = mid;
            }
        }

        if (pairs[lo].count >= target) {
            return pairs[lo].value;
        } else {. 1point3acres.com/bbs
            return pairs[hi].value;
        }
    }

    static class Pair {. visit 1point3acres.com for more.
        int value;
        long count;

        public Pair(int value, long count) {
            this.value = value;
            this.count = count;
        }
    }

    static class MyPairComparator implements Comparator<Pair> {
        @Override
        public int compare(Pair a, Pair b) {
            return a.value - b.value;
        }
    } 
}