Minimizar la diferencia absoluta máxima de elementos adyacentes en una array circular

Dada una array circular de N enteros , la tarea es minimizar la máxima diferencia absoluta de los elementos adyacentes de la array sin ninguna eliminación.

Ejemplos: 

Entrada: arr[] = {1, 3, 10, 2, 0, 9, 6} 
Salida: {0, 2, 6, 10, 9, 3, 1} 
Explicación: En el ejemplo anterior, la diferencia máxima entre elementos es 6, que está entre 9 y 3. Otros pedidos no podrán minimizarlo más.

Entrada: arr[] = {1, 2, 3, 4, 5, 6} 
Salida: {1, 3, 5, 6, 4, 2} 
Ejemplo: La diferencia máxima es 2 entre (1, 3) y (3) , 5) y (6, 4) y (4, 2). 
 

Enfoque : 
para resolver el problema, solo mostrar la array ordenada conduciría a una solución incorrecta, ya que se trata como una array circular. Después de ordenar, los últimos y primeros elementos indexados son los elementos más altos y más bajos de la array, respectivamente. Por lo tanto, la diferencia máxima entre elementos adyacentes se puede minimizar aún más. Entonces, después de ordenar, necesitamos reordenar la array ordenada de modo que los elementos indexados pares precedan a los elementos indexados impares de la array y organicen los elementos indexados impares en orden inverso.

Ilustración: Para la array dada arr[] = {1, 3, 10, 2, 0, 9, 6}, la array ordenada será {0, 1, 2, 3, 6, 9, 10}. La diferencia máxima entre elementos adyacentes en la array circular es |10 – 0| = 10 . Después de reordenar la array según el enfoque anterior, obtenemos que la array es {0, 2, 6, 10, 9, 3, 1}. Por lo tanto, la diferencia máxima ahora se minimiza a |9 – 3| = 6 . 
 

El siguiente código es la implementación del enfoque anterior: 

// C++ Program to minimize the
// maximum absolute difference
// between adjacent elements
// of the circular array
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
// Function to print the reordered array
// which minimizes the maximum absolute
// difference of adjacent elements
void solve(vector<int>& arr, int N)
{
    // Sort the given array
    sort(arr.begin(), arr.end());
    // Reorder the array
    int fl = 1,k=0;
    for(int i=0;i<=N/2;i++)
    {
        if((i%2 && fl) || !fl)
        {
            int x = arr[i];
            arr.erase(arr.begin() + i);
            arr.insert(arr.begin() + N - 1 - k, x);
            k++;
            fl = 0;
        }
    }
    // Print the new ordering
    for (int i : arr)
        cout << i << " ";
}
 
 
// Driver code
int main()
{
    int N = 7;
    vector<int> arr = {1, 3, 10, 2, 0, 9, 6};
    solve(arr, N);
     
    return 0;
}
 
// this code is contributed by divyanshu gupta

// Java program to minimize the
// maximum absolute difference
// between adjacent elements
// of the circular array
import java.util.*;
 
class GFG{
 
// Function to print the reordered array
// which minimizes the maximum absolute
// difference of adjacent elements
static void solve(Vector<Integer> arr, int N)
{
     
    // Sort the given array
    Collections.sort(arr);
     
    // Reorder the array
    int fl = 1, k = 0;
     
    for(int i = 0; i <= N / 2; i++)
    {
        if ((i % 2 != 0 && fl != 0) || fl == 0)
        {
            int x = arr.get(i);
            arr.remove(i);
            arr.add( N - 1 - k, x);
            k++;
            fl = 0;
        }
    }
     
    // Print the new ordering
    for(int i : arr)
        System.out.print(i + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int N = 7;
    Vector<Integer> arr = new Vector<>();
     
    arr.add(1);
    arr.add(3);
    arr.add(10);
    arr.add(2);
    arr.add(0);
    arr.add(9);
    arr.add(6);
     
    solve(arr, N);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 Program to minimize the
# maximum absolute difference
# between adjacent elements
# of the circular array
 
# Function to print the reordered array
# which minimizes the maximum absolute
# difference of adjacent elements
def solve(arr, N):
     
    # Sort the given array
    arr.sort(reverse = False)
     
    # Reorder the array
    fl = 1
    k=0
    for i in range(N // 2 + 1):
        if((i % 2 and fl) or fl == 0):
            x = arr[i]
            arr.remove(arr[i])
            arr.insert(N - 1 - k, x)
            k += 1
            fl = 0
             
    # Print the new ordering
    for i in arr:
        print(i, end = " ")
 
# Driver code
if __name__ == '__main__':
     
    N = 7
     
    arr = [ 1, 3, 10, 2, 0, 9, 6 ]
    solve(arr, N)
 
 
# This code is contributed by Samarth

// C# program to minimize the
// maximum absolute difference
// between adjacent elements
// of the circular array
using System;
using System.Collections.Generic;
class GFG{
 
// Function to print the
// reordered array which
// minimizes the maximum
// absolute difference of
// adjacent elements
static void solve(List<int> arr,
                  int N)
{   
  // Sort the given array
  arr.Sort();
 
  // Reorder the array
  int fl = 1, k = 0;
 
  for(int i = 0; i <= N / 2; i++)
  {
    if ((i % 2 != 0 &&
         fl != 0) || fl == 0)
    {
      int x = arr[i];
      arr.RemoveAt(i);
      arr.Insert(N - 1 - k, x);
      k++;
      fl = 0;
    }
  }
 
  // Print the new ordering
  foreach(int i in arr)
    Console.Write(i + " ");
}
 
// Driver code
public static void Main(String[] args)
{
  int N = 7;
  List<int> arr = new List<int>();
 
  arr.Add(1);
  arr.Add(3);
  arr.Add(10);
  arr.Add(2);
  arr.Add(0);
  arr.Add(9);
  arr.Add(6);
 
  solve(arr, N);
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript Program to minimize the
// maximum absolute difference
// between adjacent elements
// of the circular array
 
// Function to print the reordered array
// which minimizes the maximum absolute
// difference of adjacent elements
function solve(arr, N){
     
    // Sort the given array
    arr.sort((a,b)=>a-b)
     
    // Reorder the array
    let fl = 1
    let k=0
    for(let i=0;i<(Math.log(N / 2) + 1);i++){
        if((i % 2 && fl) || fl == 0){
            let x = arr[i]
            arr = arr.filter((y)=>y != x)
            arr.splice(N - 1 - k,0,x)
            k += 1
            fl = 0
      }
   }
             
    // Print the new ordering
    for(let i of arr)
        document.write(i," ")
}
 
// Driver code
let N = 7
     
let arr = [ 1, 3, 10, 2, 0, 9, 6 ]
solve(arr, N)
 
// This code is contributed by shinjanpatra
 
</script>

0 2 6 10 9 3 1