【HackerRank】Sherlock and MiniMax

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目连接：Sherlock and MiniMax

Watson gives Sherlock an array A1,A2...AN .
He asks him to find an integer M between P and Q (both inclusive), such that, min {|Ai-M|, 1 ≤ i ≤ N} is maximised. If there are multiple solutions, print the smallest one.

Input Format
The first line contains N . The next line contains space separated N integers, and denote the array A . The third line contains two space separated integers denoting P and Q .

Output Format
In one line, print the required answer.

Constraints
1 ≤ N ≤ 10 ²
1 ≤ Ai ≤ 10 ⁹
1 ≤ P ≤ Q ≤ 10 ⁹

Sample Input

Sample Output

题解：难度为Diffcult的一道题，真的好难=。=

首先题目理解：给定一个数组a和两个整数P和Q，在区间[P,Q]中找到一个数M，使得min{a[i] - M}最大，即对于每一个[P,Q]之间的数m，将数组中的每个数和m求差的绝对值，那么这些绝对值里面就有一个最小值(比如题目中的例子，选择m=4，那么对应的3个差的绝对值是1，4，10，最小值就是1)。现在要做的就是选出这个m，使得这个最小值最大(比如如果选定m=5，那么对应的3个差的绝对值是0，3，9，最小值是0，就比刚才选4的时候得到的最小值小，所以m选4不选5）。

首先对原数组排序，那么对于[P,Q]之间的任意一个m，对应的差的绝对值如下图两种情况所示：

图一

在第一种情况中，最小值在端点处达到；在第二种情况中，最小值在转折点处达到，这都是由a数组有序以后得到的性质。那么我们想想在哪些地方可以达到最大的最小值。如小图所示，对于任意两个数，当且仅当取m为它们的中点(a[i]+a[i+1])/2的时候，得到的最小绝对值最大。所以就可以遍历所有的(a[i],a[i+1])，然后找出使得最小值最大的m作为M。

图二

在这个过程中，有一种情况就是(a[i],a[i+1])的中点不在[P,Q]内，那么最小值或者在[P,Q]中最靠近中点处取得（区间[P,Q]和区间[a[i],a[i+1]]有交集时候，在P或者Q取到最小值）；或者[P,Q]和[a[i],a[i+1]]没有交集，即图一中第一种情况，最小值也在P或者Q处达到。那么我们为单独用O(n)的时间考察P和Q，遍历数组，找到最小值，然后查看是否可能成为最大的最小值。

总结一下算法：

首先对数组a排序
对于P和Q，利用O(N)的时间遍历数组，找到最小值，看能够成为最大的最小值；
对于任意(a[i],a[i+1])，考察(a[i]+a[i+1])/2是否在[P,Q]内，如果在，考察此处得到的最小值是否能够成为最大的最小值，注意a[i]+a[i+1]为奇数时，要考察两个中点，它们都可能取得最小值。
算法排序时间复杂度O(NlogN)，单独处理P,Q及中点复杂度O(N)，所以最终的算法时间复杂度为O(NlogN）。

代码如下：

 import java.io.*;

 import java.util.*;

 import java.math.*;

 public class Solution {

     static int miniMax = 0;

     static int miniMax_index = 0;

     private static int mini_first_last(int[] a,int first_last){

         //check for p

         int mini = Integer.MAX_VALUE;

         for(int i = 0;i < a.length;i++){

             mini = Math.min(mini,Math.abs(a[i]-first_last));

         }

         return mini;

     }

     private static void middle(int index,int[] a,int p,int q){

         int mini = Integer.MAX_VALUE;

         int mini_index = 0;

         int mid = (a[index]+a[index+1])/2;

         if(mid >= p && mid <= q){

             int m = Math.abs(a[index]-mid);

             int n = Math.abs(a[index+1]-mid);

             if(mini > Math.min(m, n)){

                 mini = Math.min(m, n);

                 mini_index = mid;

             }

             if(mid+1<=q && mid*2 != a[index] + a[index+1]){

                 m = Math.abs(a[index]-mid-1);

                 n = Math.abs(a[index+1]-mid-1);

                 if(mini > Math.min(m, n)){

                     mini = Math.min(m, n);

                     mini_index = mid+1;

                 }

             }

             if(mini != Integer.MAX_VALUE && miniMax < mini){

                 miniMax = mini;

                 miniMax_index = mini_index;

             }

         }    

     }

     public static void main(String[] args) {

         Scanner in = new Scanner(System.in);

         int n = in.nextInt();

         int[] a = new int[n];

         for(int i = 0;i < n;i++)

             a[i] = in.nextInt();

         int p = in.nextInt();

         int q = in.nextInt();

         Arrays.sort(a);

         miniMax = mini_first_last(a, p);

         miniMax_index = p;

         int temp = mini_first_last(a, q);

         if(miniMax < temp){

             miniMax = temp;

             miniMax_index = q;

         }

         for(int i = 0;i < n-1;i++){

             middle(i, a, p, q);

         }

         System.out.println(miniMax_index);

       }

 }