Número dado de páginas en n libros diferentes y m alumnos. Los libros están ordenados en orden ascendente de número de páginas. A cada estudiante se le asigna leer algunos libros consecutivos. La tarea es asignar libros de tal manera que el número máximo de páginas asignadas a un alumno sea el mínimo.
Ejemplo :
Input : pages[] = {12, 34, 67, 90} , m = 2
Output : 113
Explanation:
There are 2 number of students. Books can be distributed
in following fashion :
1) [12] and [34, 67, 90]
Max number of pages is allocated to student
'2' with 34 + 67 + 90 = 191 pages
2) [12, 34] and [67, 90]
Max number of pages is allocated to student
'2' with 67 + 90 = 157 pages
3) [12, 34, 67] and [90]
Max number of pages is allocated to student
'1' with 12 + 34 + 67 = 113 pages
Of the 3 cases, Option 3 has the minimum pages = 113.
La idea es utilizar la búsqueda binaria . Fijamos un valor para el número de páginas como la mitad del mínimo y máximo actuales. Inicializamos mínimo y máximo como 0 y suma de todas las páginas respectivamente. Si un medio actual puede ser una solución, entonces buscamos en la mitad inferior, de lo contrario buscamos en la mitad superior.
Ahora surge la pregunta, ¿cómo verificar si un valor medio es factible o no? Básicamente, debemos verificar si podemos asignar páginas a todos los estudiantes de manera que el número máximo no exceda el valor actual. Para hacer esto, asignamos páginas secuencialmente a cada estudiante mientras que el número actual de páginas asignadas no excede el valor. En este proceso, si el número de estudiantes supera m, entonces la solución no es factible. De lo contrario factible.
A continuación se muestra una implementación de la idea anterior.
C++
// C++ program for optimal allocation of pages
#include <bits/stdc++.h>
using namespace std;
// Utility function to check if current minimum value
// is feasible or not.
bool isPossible(int arr[], int n, int m, int curr_min)
{
int studentsRequired = 1;
int curr_sum = 0;
// iterate over all books
for (int i = 0; i < n; i++) {
// check if current number of pages are greater
// than curr_min that means we will get the result
// after mid no. of pages
if (arr[i] > curr_min)
return false;
// count how many students are required
// to distribute curr_min pages
if (curr_sum + arr[i] > curr_min) {
// increment student count
studentsRequired++;
// update curr_sum
curr_sum = arr[i];
// if students required becomes greater
// than given no. of students,return false
if (studentsRequired > m)
return false;
}
// else update curr_sum
else
curr_sum += arr[i];
}
return true;
}
// function to find minimum pages
int findPages(int arr[], int n, int m)
{
long long sum = 0;
// return -1 if no. of books is less than
// no. of students
if (n < m)
return -1;
// Count total number of pages
for (int i = 0; i < n; i++)
sum += arr[i];
// initialize start as 0 pages and end as
// total pages
int start = 0, end = sum;
int result = INT_MAX;
// traverse until start <= end
while (start <= end) {
// check if it is possible to distribute
// books by using mid as current minimum
int mid = (start + end) / 2;
if (isPossible(arr, n, m, mid)) {
// update result to current distribution
// as it's the best we have found till now.
result = mid;
// as we are finding minimum and books
// are sorted so reduce end = mid -1
// that means
end = mid - 1;
}
else
// if not possible means pages should be
// increased so update start = mid + 1
start = mid + 1;
}
// at-last return minimum no. of pages
return result;
}
// Drivers code
int main()
{
// Number of pages in books
int arr[] = { 12, 34, 67, 90 };
int n = sizeof arr / sizeof arr[0];
int m = 2; // No. of students
cout << "Minimum number of pages = "
<< findPages(arr, n, m) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program for optimal allocation of pages
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
// Utility function to check if current minimum value
// is feasible or not.
bool isPossible(int arr[], int n, int m, int curr_min)
{
int studentsRequired = 1;
int curr_sum = 0;
// iterate over all books
for (int i = 0; i < n; i++) {
// check if current number of pages are greater
// than curr_min that means we will get the result
// after mid no. of pages
if (arr[i] > curr_min)
return false;
// count how many students are required
// to distribute curr_min pages
if (curr_sum + arr[i] > curr_min) {
// increment student count
studentsRequired++;
// update curr_sum
curr_sum = arr[i];
// if students required becomes greater
// than given no. of students,return false
if (studentsRequired > m)
return false;
}
// else update curr_sum
else
curr_sum += arr[i];
}
return true;
}
// function to find minimum pages
int findPages(int arr[], int n, int m)
{
long long sum = 0;
// return -1 if no. of books is less than
// no. of students
if (n < m)
return -1;
// Count total number of pages
for (int i = 0; i < n; i++)
sum += arr[i];
// initialize start as 0 pages and end as
// total pages
int start = 0, end = sum;
int result = INT_MAX;
// traverse until start <= end
while (start <= end) {
// check if it is possible to distribute
// books by using mid as current minimum
int mid = (start + end) / 2;
if (isPossible(arr, n, m, mid)) {
// update result to current distribution
// as it's the best we have found till now.
result = mid;
// as we are finding minimum and books
// are sorted so reduce end = mid -1
// that means
end = mid - 1;
}
else
// if not possible means pages should be
// increased so update start = mid + 1
start = mid + 1;
}
// at-last return minimum no. of pages
return result;
}
// Drivers code
int main()
{
// Number of pages in books
int arr[] = { 12, 34, 67, 90 };
int n = sizeof arr / sizeof arr[0];
int m = 2; // No. of students
printf("Minimum number of pages = %d\n",
findPages(arr, n, m));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program for optimal allocation of pages
public class GFG
{
// Utility method to check if current minimum value
// is feasible or not.
static boolean isPossible(int arr[], int n, int m, int curr_min)
{
int studentsRequired = 1;
int curr_sum = 0;
// iterate over all books
for(int i=0;i<n;i++)
{
curr_sum += arr[i];
if(curr_sum > curr_min)
{
studentsRequired++ ; // increment student count
curr_sum = arr[i] ; // update curr_sum
}
}
return studentsRequired <= m;
}
// method to find minimum pages
static int findPages(int arr[], int n, int m)
{
int sum = 0;
// return -1 if no. of books is less than
// no. of students
if (n < m) return -1;
// Count total number of pages
for (int i = 0; i < n; i++) sum += arr[i];
// initialize start as arr[n-1] pages(minimum answer possible) and end as
// total pages(maximum answer possible)
int start = arr[n-1], end = sum;
int result = Integer.MAX_VALUE;
// traverse until start <= end
while (start <= end)
{
// check if it is possible to distribute
// books by using mid is current minimum
int mid = start + (end - start)/2;
if (isPossible(arr, n, m, mid))
{
// update result to current distribution
// as it's the best we have found till now.
result = mid;
// as we are finding minimum so,
end = mid - 1;
}
else
// if not possible, means pages should be
// increased ,so update start = mid + 1
start = mid + 1;
}
// at-last return minimum no. of pages
return result;
}
// Driver Method
public static void main(String[] args)
{
int arr[] = {12, 34, 67, 90}; //Number of pages in books
int m = 2; //No. of students
System.out.println("Minimum number of pages = " + findPages(arr, arr.length, m));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program for optimal allocation of pages
# Utility function to check if
# current minimum value is feasible or not.
def isPossible(arr, n, m, curr_min):
studentsRequired = 1
curr_sum = 0
# iterate over all books
for i in range(n):
# check if current number of pages are
# greater than curr_min that means
# we will get the result after
# mid no. of pages
if (arr[i] > curr_min):
return False
# count how many students are required
# to distribute curr_min pages
if (curr_sum + arr[i] > curr_min):
# increment student count
studentsRequired += 1
# update curr_sum
curr_sum = arr[i]
# if students required becomes greater
# than given no. of students, return False
if (studentsRequired > m):
return False
# else update curr_sum
else:
curr_sum += arr[i]
return True
# function to find minimum pages
def findPages(arr, n, m):
sum = 0
# return -1 if no. of books is
# less than no. of students
if (n < m):
return -1
# Count total number of pages
for i in range(n):
sum += arr[i]
# initialize start as 0 pages and
# end as total pages
start, end = 0, sum
result = 10**9
# traverse until start <= end
while (start <= end):
# check if it is possible to distribute
# books by using mid as current minimum
mid = (start + end) // 2
if (isPossible(arr, n, m, mid)):
# update result to current distribution
# as it's the best we have found till now.
result = mid
# as we are finding minimum and books
# are sorted so reduce end = mid -1
# that means
end = mid - 1
else:
# if not possible means pages should be
# increased so update start = mid + 1
start = mid + 1
# at-last return minimum no. of pages
return result
# Driver Code
# Number of pages in books
arr = [12, 34, 67, 90]
n = len(arr)
m = 2 # No. of students
print("Minimum number of pages = ",
findPages(arr, n, m))
# This code is contributed by Mohit Kumar
C#
// C# program for optimal
// allocation of pages
using System;
class GFG
{
// Utility function to check
// if current minimum value
// is feasible or not.
static bool isPossible(int []arr, int n,
int m, int curr_min)
{
int studentsRequired = 1;
int curr_sum = 0;
// iterate over all books
for (int i = 0; i < n; i++)
{
// check if current number of
// pages are greater than curr_min
// that means we will get the
// result after mid no. of pages
if (arr[i] > curr_min)
return false;
// count how many students
// are required to distribute
// curr_min pages
if (curr_sum + arr[i] > curr_min)
{
// increment student count
studentsRequired++;
// update curr_sum
curr_sum = arr[i];
// if students required becomes
// greater than given no. of
// students, return false
if (studentsRequired > m)
return false;
}
// else update curr_sum
else
curr_sum += arr[i];
}
return true;
}
// function to find minimum pages
static int findPages(int []arr,
int n, int m)
{
long sum = 0;
// return -1 if no. of books
// is less than no. of students
if (n < m)
return -1;
// Count total number of pages
for (int i = 0; i < n; i++)
sum += arr[i];
// initialize start as 0 pages
// and end as total pages
int start = 0, end = (int)sum;
int result = int.MaxValue;
// traverse until start <= end
while (start <= end)
{
// check if it is possible to
// distribute books by using
// mid as current minimum
int mid = (start + end) / 2;
if (isPossible(arr, n, m, mid))
{
// update result to current distribution
// as it's the best we have found till now.
result = mid;
// as we are finding minimum and
// books are sorted so reduce
// end = mid -1 that means
end = mid - 1;
}
else
// if not possible means pages
// should be increased so update
// start = mid + 1
start = mid + 1;
}
// at-last return
// minimum no. of pages
return result;
}
// Drivers code
static public void Main ()
{
//Number of pages in books
int []arr = {12, 34, 67, 90};
int n = arr.Length;
int m = 2; // No. of students
Console.WriteLine("Minimum number of pages = " +
findPages(arr, n, m));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program for optimal allocation
// of pages
// Utility function to check if current
// minimum value is feasible or not.
function isPossible($arr, $n, $m,
$curr_min)
{
$studentsRequired = 1;
$curr_sum = 0;
// iterate over all books
for ( $i = 0; $i < $n; $i++)
{
// check if current number of pages
// are greater than curr_min that
// means we will get the result
// after mid no. of pages
if ($arr[$i] > $curr_min)
return false;
// count how many students are
// required to distribute
// curr_min pages
if ($curr_sum + $arr[$i] > $curr_min)
{
// increment student count
$studentsRequired++;
// update curr_sum
$curr_sum = $arr[$i];
// if students required becomes
// greater than given no. of
// students, return false
if ($studentsRequired > $m)
return false;
}
// else update curr_sum
else
$curr_sum += $arr[$i];
}
return true;
}
// function to find minimum pages
function findPages($arr, $n, $m)
{
$sum = 0;
// return -1 if no. of books is
// less than no. of students
if ($n < $m)
return -1;
// Count total number of pages
for ($i = 0; $i < $n; $i++)
$sum += $arr[$i];
// initialize start as 0 pages
// and end as total pages
$start = 0;
$end = $sum;
$result = PHP_INT_MAX;
// traverse until start <= end
while ($start <= $end)
{
// check if it is possible to
// distribute books by using
// mid as current minimum
$mid = (int)($start + $end) / 2;
if (isPossible($arr, $n, $m, $mid))
{
// update result to current distribution
// as it's the best we have found till now
$result = $mid;
// as we are finding minimum and
// books are sorted so reduce
// end = mid -1 that means
$end = $mid - 1;
}
else
// if not possible means pages
// should be increased so update
// start = mid + 1
$start = $mid + 1;
}
// at-last return minimum
// no. of pages
return $result;
}
// Driver code
// Number of pages in books
$arr = array(12, 34, 67, 90);
$n = count($arr);
$m = 2; // No. of students
echo "Minimum number of pages = ",
findPages($arr, $n, $m), "\n";
// This code is contributed by Sach_Code
?>
Javascript
<script>
// Javascript program for optimal allocation of pages
// Utility method to check if current minimum value
// is feasible or not.
function isPossible(arr,n,m,curr_min)
{
let studentsRequired = 1;
let curr_sum = 0;
// iterate over all books
for (let i = 0; i < n; i++)
{
// check if current number of pages are greater
// than curr_min that means we will get the result
// after mid no. of pages
if (arr[i] > curr_min)
return false;
// count how many students are required
// to distribute curr_min pages
if (curr_sum + arr[i] > curr_min)
{
// increment student count
studentsRequired++;
// update curr_sum
curr_sum = arr[i];
// if students required becomes greater
// than given no. of students,return false
if (studentsRequired > m)
return false;
}
// else update curr_sum
else
curr_sum += arr[i];
}
return true;
}
// method to find minimum pages
function findPages(arr,n,m)
{
let sum = 0;
// return -1 if no. of books is less than
// no. of students
if (n < m)
return -1;
// Count total number of pages
for (let i = 0; i < n; i++)
sum += arr[i];
// initialize start as 0 pages and end as
// total pages
let start = 0, end = sum;
let result = Number.MAX_VALUE;
// traverse until start <= end
while (start <= end)
{
// check if it is possible to distribute
// books by using mid as current minimum
let mid =Math.floor( (start + end) / 2);
if (isPossible(arr, n, m, mid))
{
// if yes then find the minimum distribution
result = Math.min(result, mid);
// as we are finding minimum and books
// are sorted so reduce end = mid -1
// that means
end = mid - 1;
}
else
// if not possible means pages should be
// increased so update start = mid + 1
start = mid + 1;
}
// at-last return minimum no. of pages
return result;
}
// Driver Method
let arr=[12, 34, 67, 90];
let m = 2; //No. of students
document.write("Minimum number of pages = " +
findPages(arr, arr.length, m));
// This code is contributed by patel2127
</script>
Producción :
Minimum number of pages = 113
Complejidad de tiempo : O(N*log (M – max)), donde N es el número de libros diferentes, max denota el número máximo de páginas de todos los libros y M denota la suma del número de páginas de todos los libros diferentes Espacio
auxiliar : O(1)
Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA