Cのk人の学生に均等に配布されるチョコレートの最大数

連続したボックスに配列の形で存在するチョコレートの数と、これらのチョコレートが配布される生徒の数を表す数kが与えられます。ここでのタスクは、ボックスに存在するチョコレートの合計がk人の生徒に均等に分配されるように連続するボックスを選択することです。また、チョコレートの数が最大であることを確認する必要があります。

このために、配列を左から右にトラバースし、チョコレートの数を加算し始め、合計をkで除算します。余りが0に等しい完全に分割されている場合は、この合計を変数に格納します。さらに進むと、そのような最大の合計が得られるまでこのプロセスを繰り返します。問題は、kで割り切れる最大の合計サブアレイを見つけることです。

入力

Choco[]={ 1,2,4,5,2,8,3,5 } k=3

出力 −k人の生徒に均等に配布されるチョコレートの最大数− 5

説明 −最大合計サブ配列は{5,2,8}です。チョコレートの合計は15です。均等に割ると、3人の生徒全員が受け取るチョコレートの最大数は5です。

注 −ボックスは連続しており、インデックスは{3,4,5}

入力

Choco[] = { 2,3,7,5,4,8,2,6 } k=5

出力 −k人の生徒に均等に配布されるチョコレートの最大数− 7

説明 −最大合計サブ配列は{3,7,5,4,8,2,6}です。チョコレートの合計は35です。

均等に割ると、5人の生徒全員が受け取るチョコレートの最大数は7です。

以下のプログラムで使用されているアプローチは次のとおりです

• 連続するコンテナに多数のチョコレートを含む整数配列arr[]を使用します。

• 要素の数「n」はボックスの数を表します。

• いいえ。入力としての学生の「k」の数。

• 関数maxChocolate（int arr []、int n、int k）は、配列、そのサイズ、およびnoの3つの引数を取ります。学生のk。

• forループの使用を開始してからarr[]のトラバースを開始します。

• 2つの変数sumとmaxSumを取ります。 Sumは、サブ配列の連続する要素の合計を格納します。

• maxSumは、これまでに見つかった最大合計を格納するために使用されます。

• ネストされたforループ内で要素を追加し続け、sum％kで余りが0になるかどうかを確認します。

  また、この合計がmaxSumを超える場合は、maxSumを更新します。

• 最後に、maxSumの最大数はになります。 k人の学生の間で均等に分けることができるチョコレートの。

• 結果を、各生徒が取得するチョコレートの数であるmaxSum/kとして返します。

例

#include <stdio.h>
// to find the maximum number
// of chocolates to be distributed equally among
// k students
int maxChocolates(int arr[], int n, int k){
   int sum;
   int maxSum = 0;
   for(int i=0;i<n;i++){
      sum=0;
      for(int j=i;j<n;j++){
         sum+=arr[j];
         if(sum%k==0 && sum>maxSum)
            maxSum=sum;
      }
   }
   // distributed equally among 'k' students
   return (maxSum / k);
}
int main(){
   int arr[] = { 2, 7, 6, 1, 4, 5 ,5, 3 };
   int n =8;
   int k =3;
   printf("Maximum number of chocolates to be distributed equally among k students: %d   ",maxChocolates(arr, n, k));
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Maximum number of chocolates to be distributed equally among k students − 11