Advertisement
Guest User

Untitled

a guest
May 1st, 2016
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.60 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Solution {
  5.    
  6.     public class Range {
  7.         int start;
  8.         int end;
  9.         int value;
  10.        
  11.         public Range(int start, int end) {
  12.             this.start = start;
  13.             this.end = end;
  14.         }
  15.        
  16.         public Range(int start, int end, int value) {
  17.             this.start = start;
  18.             this.end = end;
  19.             this.value = value;
  20.         }
  21.     }
  22.  
  23.     public static void main(String[] args) {
  24.         /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
  25.         Solution sol = new Solution();
  26.         Scanner sc = new Scanner(System.in);
  27.         int numCases = sc.nextInt();
  28.         List<Integer> nums = new ArrayList<Integer>();
  29.         for (int i = 0; i < numCases; i++) {
  30.             nums.add(sc.nextInt());
  31.         }
  32.         Collections.sort(nums);
  33.         int min = sc.nextInt();
  34.         int max = sc.nextInt();
  35.         int maxNum = nums.get(nums.size()-1);
  36.         int minNum = nums.get(0);
  37.         if (minNum > max) {
  38.             System.out.println(min);
  39.         } else if (maxNum < min) {
  40.             System.out.println(max);
  41.         } else {
  42.             // Find window that you are considering
  43.             int startWindowIndex = 0;
  44.             while (nums.get(startWindowIndex) < min) {
  45.                 startWindowIndex++;
  46.             }
  47.             if (startWindowIndex > 0)
  48.                 startWindowIndex--; // Go to the element before the window starts if not already at the beginning
  49.             int endWindowIndex = startWindowIndex;
  50.             while (endWindowIndex < nums.size() - 1 && nums.get(endWindowIndex) < max) {
  51.                 endWindowIndex++;
  52.             }
  53.             int bestScore = -1;
  54.             int bestNum = -1;
  55.             if (startWindowIndex == 0) {
  56.                 // Range starts before the beginning of the array
  57.                 bestScore = Math.abs(nums.get(startWindowIndex) - min);
  58.                 bestNum = min;
  59.             }
  60.             if (nums.get(endWindowIndex) < max) {
  61.                 // Range hangs off the end of the array
  62.                 if (Math.abs(nums.get(endWindowIndex) - max) > bestScore) {
  63.                     bestScore = Math.abs(nums.get(endWindowIndex) - max);
  64.                     bestNum = max;
  65.                 }
  66.             }
  67.             // Encapsulated window
  68.             SortedMap<Integer, Range> diffs = new TreeMap<Integer, Range>();
  69.             for (int i = startWindowIndex; i < endWindowIndex; i++) {
  70.                 int upperBound = nums.get(i + 1);
  71.                 int lowerBound = nums.get(i);
  72.                 int score = (upperBound - lowerBound) / 2;
  73.                 int value = lowerBound + score;
  74.                 if (max < (lowerBound + score)) {
  75.                     score -= (lowerBound + score) - max;
  76.                     value = max;
  77.                 }
  78.                 if (min > (lowerBound + score)) {
  79.                     score -= min - (lowerBound + score);
  80.                     value = min;
  81.                 }
  82.                 if (!diffs.containsKey(score)) {
  83.                     // this assures we look at the smaller value M's first
  84.                     Range r = sol.new Range(lowerBound, upperBound);
  85.                     r.value = value;
  86.                     diffs.put(score, r);
  87.                 }
  88.             }
  89.             // Consider the biggest windows first
  90.             int maxDiff = diffs.lastKey();
  91.             if (maxDiff > bestScore) {
  92.                 bestNum = diffs.get(maxDiff).value;
  93.             }
  94.             System.out.println(bestNum);
  95.         }
  96.     }
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement