Dada una array arr[] que consiste en N enteros y un entero K , la tarea es encontrar el número máximo de inversiones posibles de la array dada después de la eliminación de K elementos de la array .
Ejemplos:
Entrada: arr[] = {2, 3, 4, 1}, K = 2
Salida: 1
Explicación: Al eliminar los elementos de array 1 y 2 , se modifica la array a {4, 1}. Por lo tanto, el número máximo de inversiones es 1.Entrada: arr[] = {4, 3, 2, 1}, K = 3
Salida: 0
Explicación: dado que la array después de K eliminaciones tendrá solo 1 elemento restante, el número máximo de inversiones es 0.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable res para almacenar el número máximo de inversiones después de eliminar K elementos de la array arr[] .
- Inicialice una string binaria S de longitud N para almacenar qué (N – K) elementos se considerarán de la array arr[] .
- Almacene 0 en posiciones [0, K – 1] que denotan K elementos eliminados, y 1 en posiciones [K, N – 1] que denotan (N – K) elementos seleccionados en la string S .
- Genere todas las permutaciones de la string S y haga lo siguiente:
- Inicialice una array v para almacenar los (N – K) elementos seleccionados de arr[] de acuerdo con la string S.
- Cuente el número de inversiones en el arreglo v y guárdelo en cnt .
- Actualice res a un máximo de res y cnt .
- Después de los pasos anteriores, imprima el valor de res como la resultante.
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 the maximum number
// of inversions after K removals
void maximizeInversions(int a[], int n,
int k)
{
// Initialize a binary string
string s;
// Iterate over range [0, K]
for (int i = 0; i < k; i++)
{
// Append 0 to the string
s += "0";
}
for (int i = k; i < n; i++)
{
// Append 1 to the string
s += "1";
}
// Stores the maximum number of
// inversions after K removals
int res = 0;
// Generate all permutations
// of string s
do
{
// Stores the current array
vector<int> v;
// Stores number of inversions
// of the current array
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
v.push_back(a[i]);
}
// Find the number of inversions
// in the array v
for (int i = 0;
i < v.size() - 1; i++)
{
for (int j = i + 1;
j < v.size(); j++)
{
// Condition to check if the
// number of pairs satisfy
// required condition
if (v[i] >= v[j])
// Increment the count
cnt++;
}
}
// Update res
res = max(res, cnt);
}
while (next_permutation(s.begin(),
s.end()));
// Print the result
cout << res;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
// Function Call
maximizeInversions(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the maximum number
// of inversions after K removals
static void maximizeInversions(int a[], int n,
int k)
{
// Initialize a binary String
String s="";
// Iterate over range [0, K]
for (int i = 0; i < k; i++)
{
// Append 0 to the String
s += "0";
}
for (int i = k; i < n; i++)
{
// Append 1 to the String
s += "1";
}
// Stores the maximum number of
// inversions after K removals
int res = 0;
// Generate all permutations
// of String s
do
{
// Stores the current array
Vector<Integer> v = new Vector<>();
// Stores number of inversions
// of the current array
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (s.charAt(i) == '1')
v.add(a[i]);
}
// Find the number of inversions
// in the array v
for (int i = 0;
i < v.size() - 1; i++)
{
for (int j = i + 1;
j < v.size(); j++)
{
// Condition to check if the
// number of pairs satisfy
// required condition
if (v.get(i) >= v.get(j))
// Increment the count
cnt++;
}
}
// Update res
res = Math.max(res, cnt);
}
while (next_permutation(s));
// Print the result
System.out.print(res);
}
static boolean next_permutation(String str)
{
char []p = str.toCharArray();
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a])
{
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return false;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 1 };
int N = arr.length;
int K = 2;
// Function Call
maximizeInversions(arr, N, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach def next_permutation(Str): p = list(Str) for a in range(len(p) - 2, -1, -1): if p[a] < p[a + 1]: b = len(p) - 1 while True: if p[b] > p[a]: t = p[a] p[a] = p[b] p[b] = t a += 1 b = len(p) - 1 while a < b: t = p[a] p[a] = p[b] p[b] = t a += 1 b -= 1 return False b -= 1 return True # Function to find the maximum number # of inversions after K removals def maximizeInversions(a, n, k): # Initialize a binary string s = "" # Iterate over range [0, K] for i in range(k): # Append 0 to the string s += "0" for i in range(k, n): # Append 1 to the string s += "1" # Stores the maximum number of # inversions after K removals res = 0 # Generate all permutations # of string s while (True): # Stores the current array v = [] # Stores number of inversions # of the current array cnt = 0 for i in range(n): if (s[i] == '1'): v.append(a[i]) # Find the number of inversions # in the array v for i in range(len(v) - 1): for j in range(i + 1, len(v)): # Condition to check if the # number of pairs satisfy # required condition if (v[i] >= v[j]): # Increment the count cnt += 1 # Update res res = max(res, cnt) if (not next_permutation(s)): break # Print the result print(res) # Driver Code arr = [ 2, 3, 4, 1 ] N = len(arr) K = 2 # Function Call maximizeInversions(arr, N, K) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the maximum number
// of inversions after K removals
static void maximizeInversions(int []a, int n,
int k)
{
// Initialize a binary String
String s="";
// Iterate over range [0, K]
for (int i = 0; i < k; i++)
{
// Append 0 to the String
s += "0";
}
for (int i = k; i < n; i++)
{
// Append 1 to the String
s += "1";
}
// Stores the maximum number of
// inversions after K removals
int res = 0;
// Generate all permutations
// of String s
do
{
// Stores the current array
List<int> v = new List<int>();
// Stores number of inversions
// of the current array
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
v.Add(a[i]);
}
// Find the number of inversions
// in the array v
for (int i = 0;
i < v.Count - 1; i++)
{
for (int j = i + 1;
j < v.Count; j++)
{
// Condition to check if the
// number of pairs satisfy
// required condition
if (v[i] >= v[j])
// Increment the count
cnt++;
}
}
// Update res
res = Math.Max(res, cnt);
}
while (next_permutation(s));
// Print the result
Console.Write(res);
}
static bool next_permutation(String str)
{
char []p = str.ToCharArray();
for (int a = p.Length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Length - 1;; --b)
if (p[b] > p[a])
{
char t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return false;
}
return true;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 3, 4, 1 };
int N = arr.Length;
int K = 2;
// Function Call
maximizeInversions(arr, N, K);
}
}
// This code contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum number
// of inversions after K removals
function maximizeInversions(a, n, k)
{
// Initialize a binary String
let s="";
// Iterate over range [0, K]
for (let i = 0; i < k; i++)
{
// Append 0 to the String
s += "0";
}
for (let i = k; i < n; i++)
{
// Append 1 to the String
s += "1";
}
// Stores the maximum number of
// inversions after K removals
let res = 0;
// Generate all permutations
// of String s
do
{
// Stores the current array
let v = [];
// Stores number of inversions
// of the current array
let cnt = 0;
for (let i = 0; i < n; i++)
{
if (s[i] == '1')
v.push(a[i]);
}
// Find the number of inversions
// in the array v
for (let i = 0;
i < v.length - 1; i++)
{
for (let j = i + 1;
j < v.length; j++)
{
// Condition to check if the
// number of pairs satisfy
// required condition
if (v[i] >= v[j])
// Increment the count
cnt++;
}
}
// Update res
res = Math.max(res, cnt);
}
while (next_permutation(s));
// Print the result
document.write(res);
}
function next_permutation(str)
{
for (let a = str.length - 2; a >= 0; --a)
if (str[a] < str[a + 1])
for (let b = str.length - 1;; --b)
if (str[b] > str[a])
{
let t = str[a];
str[a] = str[b];
str[b] = t;
for (++a, b = str.length - 1;
a < b; ++a, --b)
{
t = str[a];
str[a] = str[b];
str[b] = t;
}
return false;
}
return true;
}
// Driver Code
let arr = [ 2, 3, 4, 1 ];
let N = arr.length;
let K = 2;
// Function Call
maximizeInversions(arr, N, K);
// This code is contributed by Dharanendra L V.
</script>
Producción:
1
Complejidad de tiempo: O((N!)*(N – K) 2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA