Educational Codeforces Round 2 B. Queries about less or equal elements

链接: http://codeforces.com/contest/600/problem/B

public class TaskB {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int a = in.readInt();
        int b = in.readInt();
        int[] ary_a = in.readIntArray(a);
        int[] ary_b = in.readIntArray(b);
        shuffle(ary_a);
        Arrays.sort(ary_a);
        for (int i = 0; i < ary_b.length; i++) {
            out.print(count(ary_a, ary_b[i]) + " ");
        }
    }

    /**
     * test20卡中了sort的最慢时间, 需要先shuffle再sort
     * @param a
     */
    private static void shuffle(int[] a) {
        int n = a.length, tmp;
        for (int i = 0; i < n; ++i) {
            int r = i + (int) (Math.random() * (n - i));
            tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    private static int count(int[] ary, int n) {
        int start = 0;
        int end = ary.length;
        while (end > start) {
            int mid = start + (end - start) / 2;
            if (n >= ary[mid]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

}

这题有个test20, 卡了最差时间, 所以只是sort不行, 需要先shuffle一下. 其他就是找upper bound, 如果用c++可以直接调用模板, java没有这个函数, 所以需要写一下. count函数就是c++的upper bound, 区别只是count返回index(个数) 而upper bound返回array的元素