Educational Codeforces Round 2 B. Queries about less or equal elements
链接: http://codeforces.com/contest/600/problem/B
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
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的元素
Leave A Comment