資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告