Dada una barra de longitud L y un arreglo arr[] de longitud N , la tarea es encontrar si es posible romper la barra N-1 veces en segmentos de modo que la longitud de todos los segmentos esté presente en el arreglo. Cada vez que un segmento de longitud x se puede dividir en dos partes de longitud ⌈x/2⌉ y x – ⌈x/2⌉ .
Ejemplos:
Entrada: L = 1000, N = 1, arr[] = {1000}
Salida: SÍ
Explicación: Es posible obtener la array a realizando (N – 1 = 0) 0 operaciones en la varilla.Entrada: L = 1104, N = 2, arr[] = {861, 243}
Salida NO
Explicación: N– 1 = 1, es decir, realizar 1 operación.
Después de una operación, solo los segmentos posibles serán {552, 552}, que no están presentes en la array dada.Entrada: L = 6, N = 3, arr[] = {1, 2, 3}
Salida: SÍ
Explicación: número de operaciones = 3 – 1 = 2.
Después de una operación, la única array posible será {3, 3}.
Ahora elija el primer segmento (es decir, 3) y divídalo en dos partes, que son 1 y 2.
Después de la segunda operación, la array será = {1, 2, 3}
(Todas las permutaciones de {1, 2, 3} son aceptables, porque no importa el orden)
Enfoque: el problema se puede resolver utilizando la estructura de datos del montón según la siguiente idea:
Intente dividir ese segmento en dos partes que tiene la longitud máxima y que aún no se encuentran en la array.
Siga la ilustración que se muestra a continuación para una mejor comprensión:
Ilustración:
Considere L = 6, arr[] = {1, 2, 3}
1ra Operación:
=> Partir 6 en dos segmentos. Dos segmentos son {3, 3}.
=> Un 3 está presente en la array.2ª Operación:
=> Dividir otros 3 en dos segmentos. Dos segmentos son {1, 2}.
=> Tanto 1 como 2 están presentes en la array.Se completan dos operaciones y todas las longitudes de los segmentos también están presentes en la array.
Siga los pasos mencionados a continuación para implementar la idea:
- Coloque todos los elementos de la array en un montón máximo (por ejemplo, pqarr ).
- De manera similar, mantenga una cola de prioridad (digamos pq ) para almacenar los segmentos obtenidos después de cortar la barra y colocar L en el montón.
- Comienza a dividir desde la longitud L . En cualquier caso, será conveniente considerar el segmento más grande.
- Mientras que el montón máximo (pq) no está vacío:
- Si el elemento máximo de pq es menor que el elemento máximo de pqarr , entonces la respuesta no es posible porque ese valor de pqarr nunca se puede obtener.
- si el elemento máximo de pq es igual al elemento máximo de pqarr , elimínelo de ambos montones máximos.
- si el elemento máximo de pq es mayor que el elemento máximo de pqarr , retírelo de pq y divídalo en dos partes. Luego inserte esas dos partes en pq nuevamente.
- Una vez finalizada la iteración, si los montones están vacíos, devuelva que es posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is
// possible to arrange the array
bool solution(int len, int n, vector<int>& arr)
{
// To store elements of array
// in priorityqueue
priority_queue<int> pqarr;
// To store segments after each
// operation in priorityqueue
priority_queue<int> pq;
for (auto i : arr) {
pqarr.push(i);
}
pq.push(len);
while (pq.size() > 0) {
int elem = pqarr.top();
int cur = pq.top();
pq.pop();
if (elem > cur) {
return false;
}
if (elem == cur) {
pqarr.top();
pqarr.pop();
}
else {
pq.push(cur / 2);
pq.push((cur + 1) / 2);
}
}
return true;
}
// Driver code
int main()
{
int L = 6;
int N = 3;
vector<int> arr = { 2, 1, 3 };
// Function call
bool flag = solution(L, N, arr);
if (flag)
cout << ("YES");
else
cout << ("NO");
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java implementation of above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to check if it is
// possible to arrange the array
public static boolean solution(int len, int n,
int[] arr)
{
// To store elements of array
// in priorityqueue
PriorityQueue<Integer> pqarr = new PriorityQueue<>(Collections.reverseOrder());
// To store segments after each
// operation in priorityqueue
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i : arr) {
pqarr.add(i);
}
pq.add(len);
while (pq.size() > 0) {
int elem = pqarr.peek();
int cur = pq.poll();
if (elem > cur) {
return false;
}
if (elem == cur) {
pqarr.poll();
}
else {
pq.add(cur / 2);
pq.add((cur + 1) / 2);
}
}
return true;
}
// Driver code
public static void main(String[] args)
{
int L = 6;
int N = 3;
int[] arr = { 2, 1, 3 };
// Function call
boolean flag = solution(L, N, arr);
if (flag)
System.out.println("YES");
else
System.out.println("NO");
}
}
Python3
# Python3 implementation of above approach
import bisect
# Function to check if it is
# possible to arrange the array
def solution(length, n, arr):
# To store elements of array
# in priorityqueue
# to implement priority queue, we will use
# bisect insort to insert
#in the correct position
# and pop(-1) to get the top element
pqarr = []
# To store segments after each
#operation in priorityqueue
pq = []
for i in arr:
bisect.insort(pqarr, i)
bisect.insort(pq, length)
while (len(pq) > 0):
elem = pqarr[-1]
cur = pq[-1]
pq.pop(-1)
if elem > cur:
return False
if elem == cur:
pqarr.pop(-1)
else:
bisect.insort(pq, cur // 2)
bisect.insort(pq, (cur + 1)//2)
return True
# Driver Code
L = 6
N = 3
arr = [2, 1, 3]
# function call
flag = solution(L, N, arr)
if flag:
print("YES")
else:
print("NO")
# This code is contributed by phasing17
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to check if it is
// possible to arrange the array
public static bool solution(int len, int n,
int[] arr)
{
// To store elements of array
// in priorityqueue
List<int> pqarr = new List<int>();
// To store segments after each
// operation in priorityqueue
List<int> pq = new List<int>();
foreach (int i in arr) {
pqarr.Add(i);
}
pq.Add(len);
pqarr.Sort((a, b) => b.CompareTo(a));
pq.Sort((a, b) => b.CompareTo(a));
while (pq.Count > 0) {
int elem = pqarr[0];
int cur = pq[0];
pq.RemoveAt(0);
if (elem > cur) {
return false;
}
if (elem == cur) {
pqarr.RemoveAt(0);
}
else {
pq.Add(cur / 2);
pq.Add((cur + 1) / 2);
}
pq.Sort((a, b) => b.CompareTo(a));
}
return true;
}
// Driver code
public static void Main(String[] args)
{
int L = 6;
int N = 3;
int[] arr = { 2, 1, 3 };
// Function call
bool flag = solution(L, N, arr);
if (flag)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code contributed by shikhasingrajput
Javascript
// JavaScript implementation of above approach
// Function to check if it is
// possible to arrange the array
function solution(len, n, arr)
{
// To store elements of array
// in priorityqueue
let pqarr = [];
// To store segments after each
// operation in priorityqueue
let pq = [];
for (let i of arr)
pqarr.push(i);
pq.push(len);
pq.sort();
pq.reverse();
pqarr.sort();
pqarr.reverse();
while (pq.length > 0) {
let elem = pqarr[0];
let cur = pq[0];
pq.splice(0, 1);
if (elem > cur) {
return false;
}
if (elem == cur) {
pqarr.splice(0, 1);
}
else {
pq.push(Math.floor(cur / 2));
pq.push(Math.floor((cur + 1) / 2));
}
pq.sort();
pq.reverse();
}
return true;
}
// Driver code
let L = 6;
let N = 3;
let arr = [ 2, 1, 3 ];
// Function call
let flag = solution(L, N, arr);
if (flag)
console.log("YES");
else
console.log("NO");
// This code is contributed by phasing17
YES
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por iramkhalid24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA