Advertisement
Danielto2000

Untitled

Oct 22nd, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.34 KB | None | 0 0
  1. import java.lang.reflect.Array;
  2. import java.util.*;
  3.  
  4. public class Contest1 {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt();
  8.         int[] a = new int[n];
  9.         int k = sc.nextInt();
  10.         for (int i = 0; i < n; i++) {
  11.             a[i] = sc.nextInt();
  12.         }
  13.         int[] b = new int[k];
  14.         for (int i = 0; i < k; i++) {
  15.             b[i] = sc.nextInt();
  16.         }
  17.         System.out.println();
  18.         for (int i = 0; i < k; i++) {
  19.             int up = upperBound(a, b[i], 0, a.length - 1);
  20.             if (up >= 1) {
  21.                 if (Math.abs(a[up - 1] - b[i]) <= Math.abs(a[up] - b[i])) {
  22.                     System.out.println(a[up - 1]);
  23.                 } else System.out.println(a[up]);
  24.             } else System.out.println(a[up]);
  25.         }
  26.     }
  27.  
  28.     public static int upperBound(int[] a, int x, int left, int right) {
  29.         if (x >= a[right]) return right;
  30.         if (x < a[left]) return left;
  31.         int m = (left + right) / 2;
  32.         while (right - left > 1) {
  33.             m = (left + right) / 2;
  34.             if (a[m] <= x) {
  35.                 left = m;
  36.             } else right = m;
  37.         }
  38.         if (a[m - 1] == x && a[m] != x) return m - 1;
  39.         if (a[m + 1] > x && a[m] < x) return m + 1;
  40.         else return m;
  41.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement