Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Solution {
- public class Range {
- int start;
- int end;
- int value;
- public Range(int start, int end) {
- this.start = start;
- this.end = end;
- }
- public Range(int start, int end, int value) {
- this.start = start;
- this.end = end;
- this.value = value;
- }
- }
- public static void main(String[] args) {
- /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
- Solution sol = new Solution();
- Scanner sc = new Scanner(System.in);
- int numCases = sc.nextInt();
- List<Integer> nums = new ArrayList<Integer>();
- for (int i = 0; i < numCases; i++) {
- nums.add(sc.nextInt());
- }
- Collections.sort(nums);
- int min = sc.nextInt();
- int max = sc.nextInt();
- int maxNum = nums.get(nums.size()-1);
- int minNum = nums.get(0);
- if (minNum > max) {
- System.out.println(min);
- } else if (maxNum < min) {
- System.out.println(max);
- } else {
- // Find window that you are considering
- int startWindowIndex = 0;
- while (nums.get(startWindowIndex) < min) {
- startWindowIndex++;
- }
- if (startWindowIndex > 0)
- startWindowIndex--; // Go to the element before the window starts if not already at the beginning
- int endWindowIndex = startWindowIndex;
- while (endWindowIndex < nums.size() - 1 && nums.get(endWindowIndex) < max) {
- endWindowIndex++;
- }
- int bestScore = -1;
- int bestNum = -1;
- if (startWindowIndex == 0) {
- // Range starts before the beginning of the array
- bestScore = Math.abs(nums.get(startWindowIndex) - min);
- bestNum = min;
- }
- if (nums.get(endWindowIndex) < max) {
- // Range hangs off the end of the array
- if (Math.abs(nums.get(endWindowIndex) - max) > bestScore) {
- bestScore = Math.abs(nums.get(endWindowIndex) - max);
- bestNum = max;
- }
- }
- // Encapsulated window
- SortedMap<Integer, Range> diffs = new TreeMap<Integer, Range>();
- for (int i = startWindowIndex; i < endWindowIndex; i++) {
- int upperBound = nums.get(i + 1);
- int lowerBound = nums.get(i);
- int score = (upperBound - lowerBound) / 2;
- int value = lowerBound + score;
- if (max < (lowerBound + score)) {
- score -= (lowerBound + score) - max;
- value = max;
- }
- if (min > (lowerBound + score)) {
- score -= min - (lowerBound + score);
- value = min;
- }
- if (!diffs.containsKey(score)) {
- // this assures we look at the smaller value M's first
- Range r = sol.new Range(lowerBound, upperBound);
- r.value = value;
- diffs.put(score, r);
- }
- }
- // Consider the biggest windows first
- int maxDiff = diffs.lastKey();
- if (maxDiff > bestScore) {
- bestNum = diffs.get(maxDiff).value;
- }
- System.out.println(bestNum);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement