在C ++中分配最小页面数
分配最小页面数是一个编程问题。让我们详细讨论这个问题，看看可以解决什么问题。
声明
您将得到n本书的总页数。另外，有m个学生将要分配书籍。这些书以页数的升序排列。每个学生都可以分配一些连续的书。程序应返回学生阅读的最大页数，该页数应为最小。
让我们举个例子来更好地理解这个问题，
Input : books[] = {13 , 43, 65, 87, 92}
m = 2
Output : 179说明
在这个问题上，我们有两个正在读书的学生。因此，可以通过以下方式在它们之间分发书籍。
案例1-[13]，[43，65，87，92]
这样一来，学生可以阅读的最大页面数为13/287
案例2-[13，43]，[65，87,92]
这样一来，学生可以阅读的最大页面数为56/244
案例3-[13，43，65]，[87，92]
这样一来，学生可以阅读的最大页面数为121/179
案例4-[13，43，65，87]，[92]
这样一来，学生可以阅读的最大页面数为208/92
在所有这4种情况中，结果为179
此示例必须使您清楚地知道了问题。现在，让我们了解其背后的逻辑并为其创建程序。
为了解决这个问题，一种简单的方法是使用二进制搜索算法。对于此二进制搜索方法，请将最小和最大页面数初始化为0，并将所有书籍的页面总和初始化。然后将这些值的中间值固定为中间结果，随着算法的进行，这些中间值将发生变化。
现在，使用中间值，我们将尝试找到找到最终解决方案的可能性。如果当前的中点有机会成为解决方案，则搜索下半部分，即最小到中点。如果这种情况不成立，则搜索另一半，即中值到最大值。
该方法可用于找到该问题的解决方案，但是随着学生人数的增加，该算法往往会提供较不可靠的解决方案。
示例
#include<bits/stdc++.h>
using namespace std;
bool isPossible(int arr[], int n, int m, int curr_min) ;
int min_pages(int arr[], int n, int m) ;
int main(){
int n = 5;
int books[] = {13 , 43, 65, 87, 92};
cout<<"The number of page in books are :\n";
for(int i = 0 ; i< n; i++){
cout<<books[i]<<"\t";
}
int m = 2;
cout<<"\nMinimum number of pages = "<<min_pages(books, n, m)<<endl;
return 0;
}
bool isPossible(int arr[], int n, int m, int curr_min){
int studentsRequired = 1;
int curr_sum = 0;
for (int i = 0; i < n; i++){
if (arr[i] > curr_min)
return false;
if (curr_sum + arr[i] > curr_min){
studentsRequired++;
curr_sum = arr[i];
if (studentsRequired > m)
return false;
}
else
curr_sum += arr[i];
}
return true;
}
int min_pages(int arr[], int n, int m){
long long sum = 0;
if (n < m)
return -1;
for (int i = 0; i < n; i++)
sum += arr[i];
int minimum = 0, maximum = sum;
int result = INT_MAX;
while (minimum <= maximum){
int mid = (minimum + maximum) / 2;
if (isPossible(arr, n, m, mid)){
result = min(result, mid);
maximum = mid - 1;
}
else
minimum = mid + 1;
}
return result;
}输出结果
The number of page in books are : 13 43 65 87 92 Minimum number of pages = 179