Área más grande posible después de la eliminación de una serie de barras horizontales y verticales

Posted on by Rudeus Greyrat

Dada una cuadrícula que consta de barras horizontales y verticales de tamaño (N + 2) x (M + 2) y dos arrays H[] y V[] que indican el número de barras horizontales y verticales necesarias para eliminar, la tarea es encontrar el área más grande cuando se eliminan una serie de barras verticales y horizontales.

Ejemplos:

Entrada: N = 3, M = 3, H[] = {2}, V[] = {2}
Salida: 4
Explicación: 
Hay 3 barras en dirección horizontal y vertical. 
Después de eliminar las barras, la array se ve así:                          

Por lo tanto, el área más grande es 4.

Entrada: N = 3, M = 2, H[] = {1, 2, 3}, V[] = {1, 2}
Salida: 12

 

Enfoque: siga los pasos a continuación para resolver el problema:

  • Inicialice dos conjuntos , s1 y s2 para almacenar los enteros.
  • Iterar sobre el rango [1, N+1] y almacenar cada número entero en s1 .
  • De manera similar, itere sobre el rango [1, M + 1] y almacene cada número entero en s2 .
  • Atraviese la array H[] y elimine todo H[i] de s1.
  • De manera similar, recorra la array V[] y elimine todos los V[i] de s2.
  • Convierta los conjuntos s1 y s2 actualizados en las listas l1 y l2.
  • Ordene ambas listas en orden ascendente .
  • Recorra la lista l1 y l2 y almacene la distancia máxima entre dos vecinos como maxH y maxV respectivamente.
  • Imprime el producto de maxH y maxV como el área más grande.

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 largest area
// when a series of horizontal &
// vertical bars are removed
void largestArea(int N, int M, int H[],
                 int V[], int h, int v)
{
 
  // Stores all bars
  set<int> s1;
  set<int> s2;
 
  // Insert horizontal bars
  for (int i = 1; i <= N + 1; i++)
    s1.insert(i);
 
  // Insert vertictal bars
  for (int i = 1; i <= M + 1; i++)
    s2.insert(i);
 
  // Remove horizontal separators from s1
  for (int i = 0; i < h; i++) {
 
    s1.erase(H[i]);
  }
 
  // Remove vertical separators from s2
  for (int i = 0; i < v; i++) {
 
    s2.erase(V[i]);
  }
 
  // Stores left out horizontal and
  // vertical separators
  int list1[s1.size()];
  int list2[s2.size()];
 
  int i = 0;
  for (auto it1 = s1.begin(); it1 != s1.end(); it1++) 
  {
    list1[i++] = *it1;
  }
 
  i = 0;
  for (auto it2 = s2.begin(); it2 != s2.end(); it2++) 
  {
    list2[i++] = *it2;
  }
 
  // Sort both list in
  // ascending order
  sort(list1, list1 + s1.size());
  sort(list2, list2 + s2.size());
 
  int maxH = 0, p1 = 0, maxV = 0, p2 = 0;
 
  // Find maximum difference of neighbors of list1
  for (int j = 0; j < s1.size(); j++) {
    maxH = max(maxH, list1[j] - p1);
    p1 = list1[j];
  }
 
  // Find max difference of neighbors of list2
  for (int j = 0; j < s2.size(); j++) {
    maxV = max(maxV, list2[j] - p2);
    p2 = list2[j];
  }
 
  // Print largest volume
  cout << (maxV * maxH) << endl;
}
 
// Driver code
int main()
{
 
  // Given value of N & M
  int N = 3, M = 3;
 
  // Given arrays
  int H[] = { 2 };
  int V[] = { 2 };
 
  int h = sizeof(H) / sizeof(H[0]);
  int v = sizeof(V) / sizeof(V[0]);
 
  // Function call to find the largest
  // area when a series of horizontal &
  // vertical bars are removed
  largestArea(N, M, H, V, h, v);
 
  return 0;
}
 
// This code is contributed by divyeshrabadiya07.

Java

// Java program for the above approach
 
import java.lang.*;
import java.util.*;
 
class GFG {
 
    // Function to find the largest area
    // when a series of horizontal &
    // vertical bars are removed
    static void largestArea(int N, int M,
                            int[] H, int[] V)
    {
        // Stores all bars
        Set<Integer> s1 = new HashSet<>();
        Set<Integer> s2 = new HashSet<>();
 
        // Insert horizontal bars
        for (int i = 1; i <= N + 1; i++)
            s1.add(i);
 
        // Insert vertictal bars
        for (int i = 1; i <= M + 1; i++)
            s2.add(i);
 
        // Remove horizontal separators from s1
        for (int i = 0; i < H.length; i++) {
 
            s1.remove(H[i]);
        }
 
        // Remove vertical separators from s2
        for (int i = 0; i < V.length; i++) {
 
            s2.remove(V[i]);
        }
 
        // Stores left out horizontal and
        // vertical separators
        int[] list1 = new int[s1.size()];
        int[] list2 = new int[s2.size()];
 
        int i = 0;
        Iterator it1 = s1.iterator();
        while (it1.hasNext()) {
            list1[i++] = (int)it1.next();
        }
 
        i = 0;
        Iterator it2 = s2.iterator();
        while (it2.hasNext()) {
            list2[i++] = (int)it2.next();
        }
 
        // Sort both list in
        // ascending order
        Arrays.sort(list1);
        Arrays.sort(list2);
 
        int maxH = 0, p1 = 0, maxV = 0, p2 = 0;
 
        // Find maximum difference of neighbors of list1
        for (int j = 0; j < list1.length; j++) {
            maxH = Math.max(maxH, list1[j] - p1);
            p1 = list1[j];
        }
 
        // Find max difference of neighbors of list2
        for (int j = 0; j < list2.length; j++) {
            maxV = Math.max(maxV, list2[j] - p2);
            p2 = list2[j];
        }
 
        // Print largest volume
        System.out.println(maxV * maxH);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given value of N & M
        int N = 3, M = 3;
 
        // Given arrays
        int[] H = { 2 };
        int[] V = { 2 };
 
        // Function call to find the largest
        // area when a series of horizontal &
        // vertical bars are removed
        largestArea(N, M, H, V);
    }
}

Python3

# Python 3 program for the above approach
 
# Function to find the largest area
# when a series of horizontal &
# vertical bars are removed
def largestArea(N, M, H,
                 V, h, v):
 
  # Stores all bars
  s1 = set([]);
  s2 = set([]);
 
  # Insert horizontal bars
  for i in range(1, N + 2):
    s1.add(i);
 
  # Insert vertictal bars
  for i in range(1, M + 2):
    s2.add(i);
 
  # Remove horizontal separators from s1
  for i in range(h):
    s1.remove(H[i]);
 
  # Remove vertical separators from s2
  for i in range( v ):
 
    s2.remove(V[i]);
 
  # Stores left out horizontal and
  # vertical separators
  list1 = [0] * len(s1)
  list2 = [0]*len(s2);
 
  i = 0;
  for it1 in s1:
    list1[i] = it1;
    i += 1
 
  i = 0;
  for it2 in s2:
    list2[i] = it2
    i += 1
 
  # Sort both list in
  # ascending order
  list1.sort();
  list2.sort();
 
  maxH = 0
  p1 = 0
  maxV = 0
  p2 = 0;
 
  # Find maximum difference of neighbors of list1
  for j in range(len(s1)):
    maxH = max(maxH, list1[j] - p1);
    p1 = list1[j];
 
  # Find max difference of neighbors of list2
  for j in range(len(s2)):
    maxV = max(maxV, list2[j] - p2);
    p2 = list2[j];
 
  # Print largest volume
  print((maxV * maxH))
 
# Driver code
if __name__ == "__main__":
 
  # Given value of N & M
  N = 3
  M = 3;
 
  # Given arrays
  H = [2]
  V = [2];
 
  h = len(H)
  v = len(V);
 
  # Function call to find the largest
  # area when a series of horizontal &
  # vertical bars are removed
  largestArea(N, M, H, V, h, v);
 
  # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to find the largest area
    // when a series of horizontal &
    // vertical bars are removed
    static void largestArea(int N, int M,
                            int[] H, int[] V)
    {
        // Stores all bars
        HashSet<int> s1 = new HashSet<int>();
        HashSet<int> s2 = new HashSet<int>();
  
        // Insert horizontal bars
        for (int i = 1; i <= N + 1; i++)
            s1.Add(i);
  
        // Insert vertictal bars
        for (int i = 1; i <= M + 1; i++)
            s2.Add(i);
  
        // Remove horizontal separators from s1
        for (int i = 0; i < H.Length; i++) {
  
            s1.Remove(H[i]);
        }
  
        // Remove vertical separators from s2
        for (int i = 0; i < V.Length; i++) {
  
            s2.Remove(V[i]);
        }
  
        // Stores left out horizontal and
        // vertical separators
        int[] list1 = new int[s1.Count];
        int[] list2 = new int[s2.Count];
  
        int I = 0;
        foreach(int it1 in s1)
        {
            list1[I++] = it1;
        }
  
        I = 0;
        foreach(int it2 in s2)
        {
            list2[I++] = it2;
        }
  
        // Sort both list in
        // ascending order
        Array.Sort(list1);
        Array.Sort(list2);
  
        int maxH = 0, p1 = 0, maxV = 0, p2 = 0;
  
        // Find maximum difference of neighbors of list1
        for (int j = 0; j < list1.Length; j++) {
            maxH = Math.Max(maxH, list1[j] - p1);
            p1 = list1[j];
        }
  
        // Find max difference of neighbors of list2
        for (int j = 0; j < list2.Length; j++) {
            maxV = Math.Max(maxV, list2[j] - p2);
            p2 = list2[j];
        }
  
        // Print largest volume
        Console.WriteLine(maxV * maxH);
    }
     
  // Driver code
  static void Main()
  {
     
    // Given value of N & M
    int N = 3, M = 3;
 
    // Given arrays
    int[] H = { 2 };
    int[] V = { 2 };
 
    // Function call to find the largest
    // area when a series of horizontal &
    // vertical bars are removed
    largestArea(N, M, H, V);
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the largest area
// when a series of horizontal &
// vertical bars are removed
function largestArea(N, M, H, V, h, v)
{
 
  // Stores all bars
  var s1 = new Set();
  var s2 = new Set();
 
  // Insert horizontal bars
  for (var i = 1; i <= N + 1; i++)
    s1.add(i);
 
  // Insert vertictal bars
  for (var i = 1; i <= M + 1; i++)
    s2.add(i);
 
  // Remove horizontal separators from s1
  for (var i = 0; i < h; i++) {
 
    s1.delete(H[i]);
  }
 
  // Remove vertical separators from s2
  for (var i = 0; i < v; i++) {
 
    s2.delete(V[i]);
  }
 
  // Stores left out horizontal and
  // vertical separators
  var list1 = Array(s1.size);
  var list2 = Array(s2.size);
 
  var i = 0;
  s1.forEach(element => {
    list1[i++] = element;  
  });
  i = 0;
  s2.forEach(element => {
    list2[i++] = element;  
  });
   
 
  // Sort both list in
  // ascending order
  list1.sort((a,b)=> a-b)
  list2.sort((a,b)=> a-b)
 
  var maxH = 0, p1 = 0, maxV = 0, p2 = 0;
 
  // Find maximum difference of neighbors of list1
  for (var j = 0; j < s1.size; j++) {
    maxH = Math.max(maxH, list1[j] - p1);
    p1 = list1[j];
  }
 
  // Find max difference of neighbors of list2
  for (var j = 0; j < s2.size; j++) {
    maxV = Math.max(maxV, list2[j] - p2);
    p2 = list2[j];
  }
 
  // Print largest volume
  document.write(maxV * maxH);
}
 
// Driver code
// Given value of N & M
var N = 3, M = 3;
 
// Given arrays
var H = [2 ];
var V = [2 ];
var h = H.length;
var v = V.length;
 
// Function call to find the largest
// area when a series of horizontal &
// vertical bars are removed
largestArea(N, M, H, V, h, v);
 
// This code is contributed by rutvik_56.
</script>
Producción: 

4

 

Complejidad de tiempo: max(N, M) * (log(max(N, M)))
Espacio auxiliar : O(max(N, M))

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *