C++で最小ページ数を割り当てます

最小ページ数を割り当てることはプログラミングの問題です。この問題について詳しく話し合い、解決策を見つけましょう。

ステートメント

n冊の異なる本のページ数が与えられます 。また、m人の学生がいます 書籍の割り当て先。本はページ数の昇順で並べられています。そして、すべての学生にいくつかの連続した本を割り当てることができます。プログラムは、学生が読んだ最大ページ数を返す必要があります。これは最小でなければなりません。

この問題をよりよく理解するために例を見てみましょう。

Input : books[] = {13 , 43, 65, 87, 92}
   m = 2
Output : 179

説明

この問題では、本を読んでいる2人の生徒がいます。したがって、それらの間で本を配布するには、次の方法があります。

ケース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