数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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
在这四种情况中，结果是 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
更新于: 2019-10-16
382 次浏览
广告