Dada una array arr[] que consiste en N enteros y un entero K , la tarea es encontrar el mínimo de operaciones requeridas para hacer que todos los elementos de la array sean -1 de modo que en cada operación, elija una subarreglo de tamaño K y cambie todo el máximo elemento en el subarreglo a -1 .
Ejemplos:
Entrada: arr[] = {18, 11, 18, 11, 18}, K = 3
Salida: 3
Explicación: Las
siguientes son las operaciones realizadas:
- Al elegir la array secundaria del índice 0 a 2 y al aplicar la operación, se modifica la array a {-1, 11, -1, 11, 18}.
- Al elegir el índice de formulario de subarray 1 a 3 y al aplicar la operación, se modifica la array a {-1, -1, -1, -1, 18}.
- Al elegir el índice de formulario de subarray 2 a 4 y al aplicar la operación, se modifica la array a {-1, -1, -1, -1, -1}.
Después de las operaciones anteriores, todos los elementos de la array se convierten en -1. Por lo tanto, el número mínimo de operaciones requeridas es de 3.
Entrada: arr[] = {2, 1, 1}, K = 2
Salida: 2
Enfoque: el problema dado se puede resolver ordenando la array arr[] con índices y luego contando el número de operaciones eligiendo los elementos de la array desde el final donde la diferencia entre los índices es menor que K . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector de pares , digamos vp[] que almacena los elementos de la array con sus índices.
- Inicialice una variable, digamos minCnt como 0 que almacena el recuento del número mínimo de operaciones.
- Recorre la array arr[] y empuja la arr[i] junto con su índice i en el vector vp .
- Ordenar el vector de pares vp[] con respecto al primer valor .
- Recorra el vector vp[] hasta que no esté vacío y realice los siguientes pasos:
- Incremente el valor de minCnt en 1 .
- Extraiga todos los elementos del vector vp[] desde atrás que tengan el mismo valor (primer elemento de cada par) y que tengan diferencias entre los índices menores que K .
- Después de completar los pasos anteriores, imprima el valor de minCnt como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum the number
// of operations required to make all
// the array elements to -1
int minOperations(int arr[], int N, int K)
{
// Stores the array elements with
// their corresponding indices
vector<pair<int, int> > vp;
for (int i = 0; i < N; i++) {
// Push the array element
// and it's index
vp.push_back({ arr[i], i });
}
// Sort the elements according
// to it's first value
sort(vp.begin(), vp.end());
// Stores the minimum number of
// operations required
int minCnt = 0;
// Traverse until vp is not empty
while (!vp.empty()) {
int val, ind;
// Stores the first value of vp
val = vp.back().first;
// Stores the second value of vp
ind = vp.back().second;
// Update the minCnt
minCnt++;
// Pop the back element from the
// vp until the first value is
// same as val and difference
// between indices is less than K
while (!vp.empty()
&& vp.back().first == val
&& ind - vp.back().second + 1 <= K)
vp.pop_back();
}
// Return the minCnt
return minCnt;
}
// Driver Code
int main()
{
int arr[] = { 18, 11, 18, 11, 18 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
cout << minOperations(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find minimum the number
// of operations required to make all
// the array elements to -1
static int minOperations(int arr[], int N, int K)
{
// Stores the array elements with
// their corresponding indices
Vector<pair> vp = new Vector<pair>();
for (int i = 0; i < N; i++) {
// Push the array element
// and it's index
vp.add(new pair( arr[i], i ));
}
// Sort the elements according
// to it's first value
Collections.sort(vp,(a,b)->a.first-b.first);
// Stores the minimum number of
// operations required
int minCnt = 0;
// Traverse until vp is not empty
while (!vp.isEmpty()) {
int val, ind;
// Stores the first value of vp
val = vp.get(vp.size()-1).first;
// Stores the second value of vp
ind = vp.get(vp.size()-1).second;
// Update the minCnt
minCnt++;
// Pop the back element from the
// vp until the first value is
// same as val and difference
// between indices is less than K
while (!vp.isEmpty()
&& vp.get(vp.size()-1).first == val
&& ind - vp.get(vp.size()-1).second + 1 <= K)
vp.remove(vp.size()-1);
}
// Return the minCnt
return minCnt;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 18, 11, 18, 11, 18 };
int K = 3;
int N = arr.length;
System.out.print(minOperations(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach # Function to find minimum the number # of operations required to make all # the array elements to -1 def minOperations(arr, N, K): # Stores the array elements with # their corresponding indices vp = [] for i in range(N): # Push the array element # and it's index vp.append([arr[i], i]) # Sort the elements according # to it's first value vp.sort() # Stores the minimum number of # operations required minCnt = 0 # Traverse until vp is not empty while (len(vp) != 0): # Stores the first value of vp val = vp[-1][0] # Stores the second value of vp ind = vp[-1][1] # Update the minCnt minCnt += 1 # Pop the back element from the # vp until the first value is # same as val and difference # between indices is less than K while (len(vp) != 0 and vp[-1][0] == val and ind - vp[-1][1] + 1 <= K): vp.pop() # Return the minCnt return minCnt # Driver Code if __name__ == "__main__": arr = [18, 11, 18, 11, 18] K = 3 N = len(arr) print(minOperations(arr, N, K)) # This code is contributed by mukesh07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
class pair : IComparable<pair>
{
public int first,second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int CompareTo(pair p)
{
return this.first - p.first;
}
}
// Function to find minimum the number
// of operations required to make all
// the array elements to -1
static int minOperations(int []arr, int N, int K)
{
// Stores the array elements with
// their corresponding indices
List<pair> vp = new List<pair>();
for (int i = 0; i < N; i++) {
// Push the array element
// and it's index
vp.Add(new pair( arr[i], i ));
}
// Sort the elements according
// to it's first value
vp.Sort();
// Stores the minimum number of
// operations required
int minCnt = 0;
// Traverse until vp is not empty
while (vp.Count!=0) {
int val, ind;
// Stores the first value of vp
val = vp[vp.Count-1].first;
// Stores the second value of vp
ind = vp[vp.Count-1].second;
// Update the minCnt
minCnt++;
// Pop the back element from the
// vp until the first value is
// same as val and difference
// between indices is less than K
while (vp.Count!=0
&& vp[vp.Count-1].first == val
&& ind - vp[vp.Count-1].second + 1 <= K)
vp.RemoveAt(vp.Count-1);
}
// Return the minCnt
return minCnt;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 18, 11, 18, 11, 18 };
int K = 3;
int N = arr.Length;
Console.Write(minOperations(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find minimum the number
// of operations required to make all
// the array elements to -1
function minOperations(arr, N, K)
{
// Stores the array elements with
// their corresponding indices
let vp = [];
for (let i = 0; i < N; i++)
{
// Push the array element
// and it's index
vp.push({ "first": arr[i], "second": i });
}
// Sort the elements according
// to it's first value
vp.sort(function (a, b) { return a.first - b.first; });
// Stores the minimum number of
// operations required
let minCnt = 0;
// Traverse until vp is not empty
while (vp.length > 0) {
let val, ind;
// Stores the first value of vp
val = vp[vp.length - 1].first;
// Stores the second value of vp
ind = vp[vp.length - 1].second;
// Update the minCnt
minCnt++;
// Pop the back element from the
// vp until the first value is
// same as val and difference
// between indices is less than K
while (vp.length > 0
&& (vp[vp.length - 1].first == val)
&& (ind - vp[vp.length - 1].second + 1 <= K)) {
vp.pop();
}
}
// Return the minCnt
return minCnt;
}
// Driver Code
let arr = [18, 11, 18, 11, 18];
let K = 3;
let N = arr.length;
document.write(minOperations(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA