Dada una array arr[] de N enteros únicos, la tarea es encontrar el costo de disponerlos en un arreglo circular de tal manera que cada elemento sea menor o igual que la suma de sus elementos adyacentes.
El costo de mover un elemento del índice i en la array original al índice j en la disposición final es |i – j|
En caso de que tal arreglo no sea posible, imprima -1 .
Ejemplos:
Entrada: arr[] = {2, 4, 5, 1, 3}
Salida: 10
Explicación:
Uno de los arreglos posibles es {1, 2, 3, 4, 5}
Para índice 1, 1 ≤ 4 + 2, costo = 4 – 1 = 3
Para índice 2, 2 ≤ 1 + 3, costo = 3 + (2 – 1) = 4
Para índice 3, 3 ≤ 2 + 4, costo = 4 + (5 – 3) = 6
Para índice 4, 4 ≤ 3 + 4, costo = 6 + (4 – 2) = 8
Para el índice 5, 5 ≤ 4 + 1, costo = 8 + (5 – 3) = 10
Entrada: arr[] = {1, 10 , 100, 1000}
Salida: -1
Enfoque: el problema se puede resolver utilizando un enfoque codicioso . La idea es almacenar el índice original de los elementos en un hashmap y luego ordenar la array. Ahora comprueba si la condición dada se cumple o no. Si se determina que es cierto, calcule el costo sumando la diferencia entre los índices actuales y anteriores. De lo contrario, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if given elements
// can be arranged such that sum of
// its neighbours is strictly greater
void Arrange(int arr[], int n)
{
// Initialize the total cost
int cost = 0;
// Storing the original index of
// elements in a hashmap
unordered_map<int, int> index;
for (int i = 0; i < n; i++) {
index[arr[i]] = i;
}
// Sort the given array
sort(arr, arr + n);
// Check if a given condition
// is satisfies or not
for (int i = 0; i < n; i++) {
// First number
if (i == 0) {
if (arr[i] > arr[i + 1]
+ arr[n - 1]) {
cout << "-1";
return;
}
else {
// Add the cost to overall cost
cost += abs(index[arr[i]] - i);
}
}
// Last number
else if (i == n - 1) {
if (arr[i] > arr[i - 1]
+ arr[0]) {
cout << "-1";
return;
}
else {
// Add the cost to
// overall cost
cost += abs(index[arr[i]] - i);
}
}
else {
if (arr[i] > arr[i - 1]
+ arr[i + 1]) {
cout << "-1";
return;
}
else {
// Add the cost to
// overall cost
cost += abs(index[arr[i]] - i);
}
}
}
// Printing the cost
cout << cost;
return;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 4, 5, 1, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
Arrange(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check if given elements
// can be arranged such that sum of
// its neighbors is strictly greater
static void Arrange(int arr[], int n)
{
// Initialize the total cost
int cost = 0;
// Storing the original index of
// elements in a hashmap
HashMap<Integer,
Integer> index = new HashMap<Integer,
Integer>();
for(int i = 0; i < n; i++)
{
index.put(arr[i], i);
}
// Sort the given array
Arrays.sort(arr);
// Check if a given condition
// is satisfies or not
for(int i = 0; i < n; i++)
{
// First number
if (i == 0)
{
if (arr[i] > arr[i + 1] +
arr[n - 1])
{
System.out.print("-1");
return;
}
else
{
// Add the cost to overall cost
cost += Math.abs(index.get(arr[i]) - i);
}
}
// Last number
else if (i == n - 1)
{
if (arr[i] > arr[i - 1] +
arr[0])
{
System.out.print("-1");
return;
}
else
{
// Add the cost to
// overall cost
cost += Math.abs(index.get(arr[i]) - i);
}
}
else
{
if (arr[i] > arr[i - 1] +
arr[i + 1])
{
System.out.print("-1");
return;
}
else
{
// Add the cost to
// overall cost
cost += Math.abs(index.get(arr[i]) - i);
}
}
}
// Printing the cost
System.out.print(cost);
return;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 2, 4, 5, 1, 3 };
int N = arr.length;
// Function call
Arrange(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to check if given elements
# can be arranged such that sum of
# its neighbours is strictly greater
def Arrange(arr, n):
# Initialize the total cost
cost = 0
# Storing the original index of
# elements in a hashmap
index = {}
for i in range(n):
index[arr[i]] = i
# Sort the given array
arr.sort()
# Check if a given condition
# is satisfies or not
for i in range(n):
# First number
if(i == 0):
if(arr[i] > arr[i + 1] + arr[-1]):
print("-1")
return
else:
# Add the cost to overall cost
cost += abs(index[arr[i]] - i)
# Last number
elif(i == n - 1):
if(arr[i] > arr[i - 1] + arr[0]):
print("-1")
return
else:
# Add the cost to
# overall cost
cost += abs(index[arr[i]] - i)
else:
if(arr[i] > arr[i - 1] + arr[i + 1]):
print("-1")
return
else:
# Add the cost to
# overall cost
cost += abs(index[arr[i]] - i)
# Printing the cost
print(cost)
return
# Driver Code
# Given array
arr = [ 2, 4, 5, 1, 3 ]
N = len(arr)
# Function call
Arrange(arr, N)
# This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if given elements
// can be arranged such that sum of
// its neighbors is strictly greater
static void Arrange(int []arr, int n)
{
// Initialize the total cost
int cost = 0;
// Storing the original index of
// elements in a hashmap
Dictionary<int,
int> index = new Dictionary<int,
int>();
for(int i = 0; i < n; i++)
{
index.Add(arr[i], i);
}
// Sort the given array
Array.Sort(arr);
// Check if a given condition
// is satisfies or not
for(int i = 0; i < n; i++)
{
// First number
if (i == 0)
{
if (arr[i] > arr[i + 1] +
arr[n - 1])
{
Console.Write("-1");
return;
}
else
{
// Add the cost to overall cost
cost += Math.Abs(index[arr[i]] - i);
}
}
// Last number
else if (i == n - 1)
{
if (arr[i] > arr[i - 1] +
arr[0])
{
Console.Write("-1");
return;
}
else
{
// Add the cost to
// overall cost
cost += Math.Abs(index[arr[i]] - i);
}
}
else
{
if (arr[i] > arr[i - 1] +
arr[i + 1])
{
Console.Write("-1");
return;
}
else
{
// Add the cost to
// overall cost
cost += Math.Abs(index[arr[i]] - i);
}
}
}
// Printing the cost
Console.Write(cost);
return;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 2, 4, 5, 1, 3 };
int N = arr.Length;
// Function call
Arrange(arr, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to check if given elements
// can be arranged such that sum of
// its neighbours is strictly greater
function Arrange(arr, n)
{
// Initialize the total cost
let cost = 0;
// Storing the original index of
// elements in a hashmap
let index = new Map();
for (let i = 0; i < n; i++) {
index.set(arr[i], i)
}
// Sort the given array
arr.sort();
// Check if a given condition
// is satisfies or not
for (let i = 0; i < n; i++) {
// First number
if (i == 0) {
if (arr[i] > arr[i + 1] + arr[n - 1]) {
document.write("-1");
return;
}
else {
// Add the cost to overall cost
cost += Math.abs(index.get(arr[i]) - i);
}
}
// Last number
else if (i == n - 1) {
if (arr[i] > arr[i - 1] + arr[0]) {
document.write("-1");
return;
}
else {
// Add the cost to
// overall cost
cost += Math.abs(index.get(arr[i]) - i);
}
}
else {
if (arr[i] > arr[i - 1] + arr[i + 1]) {
document.write("-1");
return;
}
else {
// Add the cost to
// overall cost
cost += Math.abs(index.get(arr[i]) - i);
}
}
}
// Printing the cost
document.write(cost);
return;
}
// Driver Code
// Given array
let arr = [ 2, 4, 5, 1, 3 ];
let N = arr.length;
// Function call
Arrange(arr, N);
// This code is contributed by Dharanendra L V.
</script>
Producción:
10
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA