Dada una array arr[] que consta de N enteros y tres enteros X , Y y K , la tarea es encontrar el índice más lejano que se puede alcanzar mediante las siguientes operaciones:
- Si arr[i] ≥ arr[i + 1]: Pasar del índice i a i + 1 .
- Si arr[i] < arr[i+1]: Disminuya X en 1 si el valor de X > 0 o disminuya Y en (arr[i + 1] – arr[i]) si el valor de Y > (arr [i+1] – arr[i]) .
Ejemplos:
Entrada: arr[] = {4, 2, 7, 6, 9, 14, 12}, X = 1, Y = 5, K = 0
Salida: 4
Explicación:
Inicialmente, K = 0.
arr[0] > arr [1]: Por lo tanto, muévase al índice 1.
arr[1] < arr[2]: Decremente X en 1 y muévase al índice 2. Ahora X = 0.
arr[2] > arr[3]: Muévase al índice 3 .arr
[3] < arr[4]: Decrementa Y en 3 y pasa al índice 4. Ahora Y = 2
arr[4] < arr[5]: Ni X > 0 ni Y > 5. Por lo tanto, no es posible para pasar al índice siguiente.
Por lo tanto, el índice máximo que se puede alcanzar es 4.Entrada: arr[] = {14, 3, 19, 3}, X = 17, Y = 0, K = 1
Salida: 3
Enfoque: La idea es usar X para la diferencia máxima entre índices e Y para la diferencia restante. Siga los pasos a continuación para resolver este problema:
- Declarar una cola de prioridad .
- Recorra la array dada arr[] y realice las siguientes operaciones:
- Si el elemento actual ( arr[i] ) es mayor que el siguiente elemento ( arr[i + 1] ), pase al siguiente índice.
- De lo contrario, inserte la diferencia de (arr[i + 1] – arr[i]) en la cola de prioridad .
- Si el tamaño de la cola de prioridad es mayor que Y , disminuya X por el elemento superior de la cola de prioridad y extraiga ese elemento.
- Si X es menor que 0 , el índice más lejano que se puede alcanzar es i .
- Después de completar los pasos anteriores, si el valor de X es al menos 0 , entonces el índice más lejano que se puede alcanzar es (N – 1) .
A continuación se muestra la implementación del enfoque anterior:
Java
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the farthest index
// that can be reached
void farthestHill(int arr[], int X,
int Y, int N, int K)
{
int i, diff;
// Declare a priority queue
priority_queue<int> pq;
// Iterate the array
for (i = K; i < N - 1; i++) {
// If current element is
// greater than the next element
if (arr[i] >= arr[i + 1])
continue;
// Otherwise, store their difference
diff = arr[i + 1] - arr[i];
// Push diff into pq
pq.push(diff);
// If size of pq exceeds Y
if (pq.size() > Y) {
// Decrease X by the
// top element of pq
X -= pq.top();
// Remove top of pq
pq.pop();
}
// If X is exhausted
if (X < 0) {
// Current index is the
// farthest possible
cout << i;
return;
}
}
// Print N-1 as farthest index
cout << N - 1;
}
// Driver Code
int main()
{
int arr[] = { 4, 2, 7, 6, 9, 14, 12 };
int X = 5, Y = 1;
int K = 0;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
farthestHill(arr, X, Y, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the farthest index
// that can be reached
public static void farthestHill(int arr[], int X,
int Y, int N, int K)
{
int i, diff;
// Declare a priority queue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// Iterate the array
for(i = K; i < N - 1; i++)
{
// If current element is
// greater than the next element
if (arr[i] >= arr[i + 1])
continue;
// Otherwise, store their difference
diff = arr[i + 1] - arr[i];
// Push diff into pq
pq.add(diff);
// If size of pq exceeds Y
if (pq.size() > Y)
{
// Decrease X by the
// top element of pq
X -= pq.peek();
// Remove top of pq
pq.poll();
}
// If X is exhausted
if (X < 0)
{
// Current index is the
// farthest possible
System.out.print(i);
return;
}
}
// Print N-1 as farthest index
System.out.print(N - 1);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 2, 7, 6, 9, 14, 12 };
int X = 5, Y = 1;
int K = 0;
int N = arr.length;
// Function Call
farthestHill(arr, X, Y, N, K);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach # Function to find the farthest index # that can be reached def farthestHill(arr, X, Y, N, K): # Declare a priority queue pq = [] # Iterate the array for i in range(K, N - 1, 1): # If current element is # greater than the next element if (arr[i] >= arr[i + 1]): continue # Otherwise, store their difference diff = arr[i + 1] - arr[i] # Push diff into pq pq.append(diff) # If size of pq exceeds Y if (len(pq) > Y): # Decrease X by the # top element of pq X -= pq[-1] # Remove top of pq pq[-1] # If X is exhausted if (X < 0): # Current index is the # farthest possible print(i) return # Print N-1 as farthest index print(N - 1) # Driver Code arr = [ 4, 2, 7, 6, 9, 14, 12 ] X = 5 Y = 1 K = 0 N = len(arr) # Function Call farthestHill(arr, X, Y, N, K) # This code is contributed by code_hunt
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the farthest index
// that can be reached
public static void farthestHill(int[] arr, int X,
int Y, int N, int K)
{
int i, diff;
// Declare a priority queue
List<int> pq = new List<int>();
// Iterate the array
for(i = K; i < N - 1; i++)
{
// If current element is
// greater than the next element
if (arr[i] >= arr[i + 1])
continue;
// Otherwise, store their difference
diff = arr[i + 1] - arr[i];
// Push diff into pq
pq.Add(diff);
pq.Sort();
pq.Reverse();
// If size of pq exceeds Y
if (pq.Count > Y)
{
// Decrease X by the
// top element of pq
X -= pq[0];
// Remove top of pq
pq.RemoveAt(0);
}
// If X is exhausted
if (X < 0)
{
// Current index is the
// farthest possible
Console.Write(i);
return;
}
}
// Print N-1 as farthest index
Console.Write(N - 1);
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 4, 2, 7, 6, 9, 14, 12 };
int X = 5, Y = 1;
int K = 0;
int N = arr.Length;
// Function Call
farthestHill(arr, X, Y, N, K);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to find the farthest index
// that can be reached
function farthestHill(arr, X, Y, N, K)
{
var i, diff;
// Declare a priority queue
var pq = [];
// Iterate the array
for(i = K; i < N - 1; i++)
{
// If current element is
// greater than the next element
if (arr[i] >= arr[i + 1])
continue;
// Otherwise, store their difference
diff = arr[i + 1] - arr[i];
// Push diff into pq
pq.push(diff);
pq.sort();
pq = pq.reverse();
// If size of pq exceeds Y
if (pq.length > Y)
{
// Decrease X by the
// top element of pq
X -= pq[0];
// Remove top of pq
pq = pq.slice(1);
}
// If X is exhausted
if (X < 0)
{
// Current index is the
// farthest possible
document.write(i);
return;
}
}
// Print N-1 as farthest index
document.write(N - 1);
}
// Driver code
var arr = [4, 2, 7, 6, 9, 14, 12];
var X = 5, Y = 1;
var K = 0;
var N = arr.length;
// Function Call
farthestHill(arr, X, Y, N, K);
// This code is contributed by SURENDRA_GANGWAR.
</script>
Producción:
4
Complejidad de tiempo: O(N*log(E)), donde E es el número máximo de elementos en la cola de prioridad.
Espacio Auxiliar: O(E)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA