Dada una string que consta de solo 0 y 1. Ahora tiene N rangos que no se cruzan L, R ( L <= R), más específicamente [L1, R1], [L2, R2], …, [LN, RN], ninguno de estos intervalos se superponen, formalmente, para cada i, j válido tal que i!=j, ya sea Ri<Lj o Rj<Li.
La tarea es encontrar una permutación válida que contenga las dos condiciones siguientes simultáneamente:
- La suma de los números entre todos los N rangos dados será el máximo.
- La string será lexicográficamente más grande. Una string 1100 es lexicográficamente más grande que la string 1001.
Ejemplos:
Entrada
11100
2
2 3
5 5
Salida
01101
Primero ponemos 1 en la posición 2 y 3 luego en 5 ya
que no quedan 1, la string formada es 01101.
Entrada
0000111
2
1 1
1 2
Salida
1110000
En el ejemplo anterior, nosotros, Primero, coloque 1 en la primera y segunda posición, luego nos queda otro ‘1’.
Entonces, lo usamos para maximizar la string lexicográficamente y lo colocamos en la tercera posición y, por lo tanto, la reorganización está completa.
Acercarse
- Se da prioridad a hacer que el recuento de 1 entre todos los l y r sea máx. Contamos el número de 1 en la array y los almacenamos en una variable.
- Después de tomar la entrada, actualizamos el rango de cada l y r por 1 para marcar la posición que se llenará con 1 primero.
- Luego, tomamos la suma del prefijo de la array para obtener la posición donde fijar los 1 primero. Luego ejecutamos un ciclo en esa array de suma de prefijos desde la izquierda. Si obtenemos alguna posición con un valor mayor a 1, eso significa que tenemos un lr en ese índice. Continuamos poniendo 1 en esos índices hasta que la cuenta de 1 se vuelve cero.
- Ahora, una vez finalizada la operación de maximización y si quedan algunos 1, entonces comenzamos la maximización lexicográfica. Nuevamente comenzamos un ciclo desde la izquierda de la array de suma de prefijos. Si encontramos un índice que tiene el valor 0 que indica que no hay lr que tenga ese índice, entonces ponemos un 1 en ese índice y así continuamos hasta que se llenan todos los 1 restantes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
void arrange(string s)
{
int cc = 0;
// Storing the count of 1's in the string
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '1') cc++;
}
int a[s.length() + 1] = {0};
// Query of l and r
int qq[][2] = {{2, 3}, {5, 5}};
int n = sizeof(qq) / sizeof(qq[0]);
for (int i = 0; i < n; i++)
{
int l = qq[i][0], r = qq[i][1];
l--, r--;
a[l]++;
// Applying range update technique.
a[r + 1]--;
}
int len_a = sizeof(a) / sizeof(a[0]);
for (int i = 1; i < len_a; i++)
{
// Taking prefix sum to get the range update values
a[i] += a[i - 1];
}
// Final array which will store the arranged string
int zz[s.length()] = {0};
for (int i = 0; i < len_a - 1; i++)
{
if (a[i] > 0)
{
if (cc > 0)
{
zz[i] = 1;
cc--;
}
else
break;
}
if (cc == 0) break;
}
// if after maximizing the ranges any 1 is left
// then we maximize the string lexicographically.
if (cc > 0)
{
for (int i = 0; i < s.length(); i++)
{
if (zz[i] == 0)
{
zz[i] = 1;
cc--;
}
if (cc == 0) break;
}
}
for (int i = 0; i < s.length(); i++)
cout << zz[i];
cout << endl;
}
// Driver Code
int main()
{
string str = "11100";
arrange(str);
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java implementation of the approach
class GFG
{
static void arrange(String s)
{
int cc = 0;
// Storing the count of 1's in the String
for (int i = 0; i < s.length(); i++)
{
if (s.charAt(i) == '1') cc++;
}
int []a = new int[s.length() + 1];
// Query of l and r
int qq[][] = {{2, 3}, {5, 5}};
int n = qq.length;
for (int i = 0; i < n; i++)
{
int l = qq[i][0], r = qq[i][1];
l--; r--;
a[l]++;
// Applying range update technique.
a[r + 1]--;
}
int len_a = a.length;
for (int i = 1; i < len_a; i++)
{
// Taking prefix sum to get the range update values
a[i] += a[i - 1];
}
// Final array which will store the arranged String
int []zz = new int[s.length()];
for (int i = 0; i < len_a - 1; i++)
{
if (a[i] > 0)
{
if (cc > 0)
{
zz[i] = 1;
cc--;
}
else
break;
}
if (cc == 0) break;
}
// if after maximizing the ranges any 1 is left
// then we maximize the String lexicographically.
if (cc > 0)
{
for (int i = 0; i < s.length(); i++)
{
if (zz[i] == 0)
{
zz[i] = 1;
cc--;
}
if (cc == 0) break;
}
}
for (int i = 0; i < s.length(); i++)
System.out.print(zz[i]);
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
String str = "11100";
arrange(str);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation of the approach def arrange(s): cc = 0 # Storing the count of 1's in the string for i in range(len(s)): if(s[i]=="1"): cc+= 1 a =[0]*(len(s)+1) # Query of l and r qq =[(2, 3), (5, 5)] n = len(qq) for i in range(n): l, r = qq[i][0], qq[i][1] l-= 1 r-= 1 a[l]+= 1 # Applying range update technique. a[r + 1]-= 1 for i in range(1, len(a)): # Taking prefix sum to get the range update values a[i]= a[i]+a[i-1] # Final array which will store the arranged string zz =[0]*len(s) for i in range(len(a)-1): if(a[i]>0): if(cc>0): zz[i]= 1 cc-= 1 else: break if(cc == 0): break # if after maximizing the ranges any 1 is left # then we maximize the string lexicographically. if(cc>0): for i in range(len(s)): if(zz[i]== 0): zz[i]= 1 cc-= 1 if(cc == 0): break print(*zz, sep ="") str = "11100" arrange(str)
C#
// C# implementation of the approach
using System;
class GFG
{
static void arrange(String s)
{
int cc = 0;
// Storing the count of 1's in the String
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '1') cc++;
}
int []a = new int[s.Length + 1];
// Query of l and r
int [,]qq = {{2, 3}, {5, 5}};
int n = qq.GetLength(0);
for (int i = 0; i < n; i++)
{
int l = qq[i, 0], r = qq[i, 1];
l--; r--;
a[l]++;
// Applying range update technique.
a[r + 1]--;
}
int len_a = a.Length;
for (int i = 1; i < len_a; i++)
{
// Taking prefix sum to get the range update values
a[i] += a[i - 1];
}
// Final array which will store the arranged String
int []zz = new int[s.Length];
for (int i = 0; i < len_a - 1; i++)
{
if (a[i] > 0)
{
if (cc > 0)
{
zz[i] = 1;
cc--;
}
else
break;
}
if (cc == 0) break;
}
// if after maximizing the ranges any 1 is left
// then we maximize the String lexicographically.
if (cc > 0)
{
for (int i = 0; i < s.Length; i++)
{
if (zz[i] == 0)
{
zz[i] = 1;
cc--;
}
if (cc == 0) break;
}
}
for (int i = 0; i < s.Length; i++)
Console.Write(zz[i]);
Console.WriteLine();
}
// Driver Code
public static void Main(String[] args)
{
String str = "11100";
arrange(str);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
function arrange(s)
{
var cc = 0;
// Storing the count of 1's in the string
for(var i = 0; i < s.length; i++)
{
if (s[i] == '1') cc++;
}
var a = Array(s.length+1).fill(0);
// Query of l and r
var qq = [[2, 3], [5, 5]];
var n = qq.length;
for (var i = 0; i < n; i++)
{
var l = qq[i][0], r = qq[i][1];
l--, r--;
a[l]++;
// Applying range update technique.
a[r + 1]--;
}
var len_a = a.length;
for (var i = 1; i < len_a; i++)
{
// Taking prefix sum to get the range update values
a[i] += a[i - 1];
}
// Final array which will store the arranged string
var zz = Array(s.length).fill(0);
for (var i = 0; i < len_a - 1; i++)
{
if (a[i] > 0)
{
if (cc > 0)
{
zz[i] = 1;
cc--;
}
else
break;
}
if (cc == 0) break;
}
// if after maximizing the ranges any 1 is left
// then we maximize the string lexicographically.
if (cc > 0)
{
for (var i = 0; i < s.length; i++)
{
if (zz[i] == 0)
{
zz[i] = 1;
cc--;
}
if (cc == 0) break;
}
}
for (var i = 0; i < s.length; i++)
document.write( zz[i]);
document.write("<br>");
}
// Driver Code
var str = "11100";
arrange(str);
</script>
Producción:
01101