Digamos que tenemos un párrafo como este:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed tempor y vitalidad, de modo que el trabajo y el dolor, algunas cosas importantes que hacer eiusmod. A lo largo de los años, vendré, quien no sacará alícuotas de ella la ventaja del ejercicio, para que los esfuerzos de estímulo si el distrito escolar y la longevidad. Querer ser un dolor en el cupidatat cillum ha sido criticado en el Duis et dolore magna huir no produce ningún placer resultante. Los negros excepteur cupidatat no son excepteur, es reconfortante para el alma, es decir, abandonaron los deberes generales de los que tienen la culpa de tus problemas.
Suponiendo una fuente de ancho fijo, queremos agregar exactamente N saltos de línea (reemplazando solo los caracteres de espacio) para producir un bloque de texto de N + 1 líneas.
Aquí hay un ejemplo de salida para N = 8, obtenemos un ancho de línea máximo de 51:
Lorem ipsum dolor sit amet, consectetur adipiscing
elit, sed do eiusmod tempor incididunt ut labore
et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat. Duis aute irure
dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur
sint occaecat cupidatat non proident, sunt in culpa
qui officia deserunt mollit anim id est laborum.
¿Cómo encontramos qué caracteres de espacio reemplazar con saltos de línea para obtener el menor número de caracteres en la línea más larga con el menor número de intentos?
(Adaptado de aquí, ¿Cómo particionar una matriz de enteros de una manera que minimice el máximo de la suma de cada partición? )
Si consideramos las longitudes de las palabras como una lista de números, podemos realizar una búsqueda binaria en la partición.
Nuestros max lengthrangos de 0a sum (word-length list) + (num words - 1), meaning the spaces. mid = (range / 2). Verificamos si midse puede lograr dividiendo en Nconjuntos en el O(m)tiempo: recorra la lista, agregando (word_length + 1)a la parte actual mientras que la suma actual es menor o igual a mid. Cuando pase la suma mid, comience una nueva parte. Si el resultado incluye No menos partes, mides alcanzable.
Si midse puede lograr, pruebe con un rango más bajo; de lo contrario, un rango más alto. La complejidad del tiempo es O(m log num_chars). (También tendrá que considerar cómo eliminar un espacio por parte, es decir, dónde iría el salto de línea, las características en el cálculo).
Este artículo se recopila de Internet, indique la fuente cuando se vuelva a imprimir.
En caso de infracción, por favor [email protected] Eliminar
Déjame decir algunas palabras