在k名学生中平均分配的巧克力的最大数量-yiteyi-C++库

鉴于 N 装有巧克力的盒子排成一排。有 K 学生人数。问题是在每个人之间平均分配最大数量的巧克力 K 学生从给定的批次中选择连续的盒子序列。考虑盒子是排成一行的，数字从1到n从左到右。我们必须选择一组连续排列的盒子，这样才能为所有顾客提供最多数量的巧克力 K 学生。阵列 arr[] 表示盒子的行排列，arr[i]表示盒子中“i”位置的巧克力数量。 例如：

null

Input : arr[] = {2, 7, 6, 1, 4, 5}, k = 3Output : 6The subarray is {7, 6, 1, 4} with sum 18.Equal distribution of 18 chocolates among3 students is 6.Note that the selected boxes are in consecutive orderwith indexes {1, 2, 3, 4}.

资料来源： 亚马逊问道。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

问题是找到可被k整除的最大和子数组，然后返回（sum/k）。 方法1（天真的方法）： 考虑所有子阵列的和。选择最大和。顺其自然 maxSum 回来 （最大值/k） 时间复杂度为O（n） ^2. ). 方法2（有效方法）： 创建一个数组 总和[] 哪里 总和[i] 商店 总和（arr[0]+…arr[i]） .创建一个哈希表，将元组作为 （ele，idx） ，其中ele表示 （总和[i]%k） 和 idx 表示数组中第一次出现的元素的索引 总和[] 正在从左向右移动。现在横穿 总和[] 从i=0到n，并遵循下面给出的步骤。

将当前余数计算为 curr_rem =总和[i]%k。
如果curr_rem==0，则检查maxSum是否 maxSum =sum[i]。
否则如果 curr_rem 哈希表中不存在，然后创建元组 （curr_-rem，i） 在哈希表中。
否则，获取与 curr_rem 在哈希表中。就这样吧 idx .现在，如果maxSum maxSum =sum[i]–sum[idx]。

最后，返回 （最大值/k） . 说明： 如果（sum[i]%k）=（sum[j]%k），其中sum[i]=sum（arr[0]+..+arr[i]）和sum[j]=sum（arr[0]+..+arr[j]）且“i”小于“j”，那么sum（arr[i+1]+..+arr[j]）必须能被“k”整除。

C++

                         // C++ implementation to find the maximum number                       
                         // of chocolates to be distributed equally among                       
                         // k students                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to find the maximum number of chocolates                       
                         // to be distributed equally among k students                       
                         int                                     maxNumOfChocolates(                                     int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // unordered_map 'um' implemented as                       
                                                 // hash table                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > um;                       
           
                                                 // 'sum[]' to store cumulative sum, where                       
                                                 // sum[i] = sum(arr[0]+..arr[i])                       
                                                 int                                     sum[n], curr_rem;                       
           
                                                 // to store sum of sub-array having maximum sum                       
                                                 int                                     maxSum = 0;                       
           
                                                 // building up 'sum[]'                       
                                                 sum[0] = arr[0];                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 sum[i] = sum[i - 1] + arr[i];                       
           
                                                 // traversing 'sum[]'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // finding current remainder                       
                                                 curr_rem = sum[i] % k;                       
           
                                                 // if true then sum(0..i) is divisible                       
                                                 // by k                       
                                                 if                                     (curr_rem == 0) {                       
                                                 // update 'maxSum'                       
                                                 if                                     (maxSum < sum[i])                       
                                                 maxSum = sum[i];                       
                                                 }                       
           
                                                 // if value 'curr_rem' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (um.find(curr_rem) == um.end())                       
                                                 um[curr_rem] = i;                       
           
                                                 else                       
                                                 // if true, then update 'max'                       
                                                 if                                     (maxSum < (sum[i] - sum[um[curr_rem]]))                       
                                                 maxSum = sum[i] - sum[um[curr_rem]];                       
                                                 }                       
           
                                                 // required maximum number of chocolates to be                       
                                                 // distributed equally among 'k' students                       
                                                 return                                     (maxSum / k);                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 7, 6, 1, 4, 5 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 3;                       
                                                 cout <<                                     "Maximum number of chocolates: "                       
                                                 << maxNumOfChocolates(arr, n, k);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to find the maximum number                       
                         // of chocolates to be distributed equally among                       
                         // k students                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
                         class                                     GFG {                       
                         // Function to find the maximum number of chocolates                       
                         // to be distributed equally among k students                       
                         static                                     int                                     maxNumOfChocolates(                                     int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // Hash table                       
                                                 HashMap <Integer,Integer> um =                                     new                                     HashMap<Integer,Integer>();                       
           
                                                 // 'sum[]' to store cumulative sum, where                       
                                                 // sum[i] = sum(arr[0]+..arr[i])                       
                                                 int                                     [] sum=                                     new                                     int                                     [n];                       
                                                 int                                     curr_rem;                       
           
                                                 // To store sum of sub-array having maximum sum                       
                                                 int                                     maxSum =                                     0                                     ;                       
           
                                                 // Building up 'sum[]'                       
                                                 sum[                                     0                                     ] = arr[                                     0                                     ];                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 sum[i] = sum[i -                                     1                                     ] + arr[i];                       
           
                                                 // Traversing 'sum[]'                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
           
                                                 // Finding current remainder                       
                                                 curr_rem = sum[i] % k;                       
           
                                                 // If true then sum(0..i) is divisible                       
                                                 // by k                       
                                                 if                                     (curr_rem ==                                     0                                     ) {                       
                                                 // update 'maxSum'                       
                                                 if                                     (maxSum < sum[i])                       
                                                 maxSum = sum[i];                       
                                                 }                       
           
                                                 // If value 'curr_rem' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (!um.containsKey(curr_rem) )                       
                                                 um.put(curr_rem , i);                       
           
                                                 else                       
                                                 // If true, then update 'max'                       
                                                 if                                     (maxSum < (sum[i] - sum[um.get(curr_rem)]))                       
                                                 maxSum = sum[i] - sum[um.get(curr_rem)];                       
                                                 }                       
           
                                                 // Required maximum number of chocolates to be                       
                                                 // distributed equally among 'k' students                       
                                                 return                                     (maxSum / k);                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                         int                                     arr[] = {                                     2                                     ,                                     7                                     ,                                     6                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     };                       
                         int                                     n = arr.length;                       
                         int                                     k =                                     3                                     ;                       
                         System.out.println(                                     "Maximum number of chocolates: "                       
                                                 + maxNumOfChocolates(arr, n, k));                       
                         }                       
                                                 }                       
           
                         // This code is contributed by 'Gitanjali'.                       

Python3

                         # Python3 implementation to                       
                         # find the maximum number                       
                         # of chocolates to be                       
                         # distributed equally                       
                         # among k students                       
           
                         # function to find the                       
                         # maximum number of chocolates                       
                         # to be distributed equally                       
                         # among k students                       
                         def                                     maxNumOfChocolates(arr, n, k):                       
                                   
                                                 um, curr_rem, maxSum                                     =                                     {},                                     0                                     ,                                     0                       
                                   
                                                 # 'sm[]' to store cumulative sm,                       
                                                 # where sm[i] = sm(arr[0]+..arr[i])                       
                                                 sm                                     =                                     [                                     0                                     ]                                     *                                     n                       
                                                 sm[                                     0                                     ]                                     =                                     arr[                                     0                                     ]                       
                                   
                                                 # building up 'sm[]'                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 sm[i]                                     =                                     sm[i                                     -                                     1                                     ]                                     +                                     arr[i]                       
                                   
                                                 # traversing 'sm[]'                       
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # finding current remainder                       
                                                 curr_rem                                     =                                     sm[i]                                     %                                     k                       
                                   
                                                 if                                     (                                     not                                     curr_rem                                     and                                     maxSum < sm[i]) :                       
                                                 maxSum                                     =                                     sm[i]                       
                                                 elif                                     (                                     not                                     curr_rem                                     in                                     um) :                       
                                                 um[curr_rem]                                     =                                     i                       
                                                 elif                                     (maxSum < (sm[i]                                     -                                     sm[um[curr_rem]])):                       
                                                 maxSum                                     =                                     sm[i]                                     -                                     sm[um[curr_rem]]                       
                                   
                                                 return                                     maxSum                                     /                                     /                                     k                       
                                   
                         # Driver program to test above                       
                         arr                                     =                                     [                                     2                                     ,                                     7                                     ,                                     6                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     ]                       
                         n, k                                     =                                     len                                     (arr),                                     3                       
           
                         print                                     (                                     "Maximum number of chocolates: "                                     +                       
                                                 str                                     (maxNumOfChocolates(arr, n, k)))                       
           
                         # This code is contributed by Ansu Kumari                       

C#

                         // C# implementation to find                       
                         // the maximum number of                       
                         // chocolates to be distributed                       
                         // equally among k students                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Function to find the                       
                                                 // maximum number of                       
                                                 // chocolates to be distributed                       
                                                 // equally among k students                       
                                                 static                                     int                                     maxNumOfChocolates(                                     int                                     []arr,                       
                                                 int                                     n,                                     int                                     k)                       
                                                 {                       
                                                 // Hash table                       
                                                 Dictionary <                                     int                                     ,                                     int                                     > um =                       
                                                 new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
                                   
                                                 // 'sum[]' to store cumulative                       
                                                 // sum, where sum[i] =                       
                                                 // sum(arr[0]+..arr[i])                       
                                                 int                                     [] sum =                                     new                                     int                                     [n];                       
                                                 int                                     curr_rem;                       
                                   
                                                 // To store sum of sub-array                       
                                                 // having maximum sum                       
                                                 int                                     maxSum = 0;                       
                                   
                                                 // Building up 'sum[]'                       
                                                 sum[0] = arr[0];                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 sum[i] = sum[i - 1] + arr[i];                       
                                   
                                                 // Traversing 'sum[]'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // Finding current                       
                                                 // remainder                       
                                                 curr_rem = sum[i] % k;                       
                                   
                                                 // If true then sum(0..i)                       
                                                 // is divisible by k                       
                                                 if                                     (curr_rem == 0)                       
                                                 {                       
                                                 // update 'maxSum'                       
                                                 if                                     (maxSum < sum[i])                       
                                                 maxSum = sum[i];                       
                                                 }                       
                                   
                                                 // If value 'curr_rem' not                       
                                                 // present in 'um' then store                       
                                                 // it in 'um' with index of                       
                                                 // its first occurrence                       
                                                 else                                     if                                     (!um.ContainsKey(curr_rem))                       
                                                 um.Add(curr_rem , i);                       
                                   
                                                 else                       
                                   
                                                 // If true, then                       
                                                 // update 'max'                       
                                                 if                                     (maxSum < (sum[i] -                       
                                                 sum[um[curr_rem]]))                       
                                                 maxSum = sum[i] -                       
                                                 sum[um[curr_rem]];                       
                                                 }                       
                                   
                                                 // Required maximum number                       
                                                 // of chocolates to be                       
                                                 // distributed equally                       
                                                 // among 'k' students                       
                                                 return                                     (maxSum / k);                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr =                                     new                                     int                                     []{ 2, 7, 6, 1, 4, 5 };                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     k = 3;                       
                                                 Console.Write(                                     "Maximum number of chocolates: "                                     +                       
                                                 maxNumOfChocolates(arr, n, k));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // Manish Shaw(manishshaw1)                       

Javascript

                         <script>                       
           
                         // Javascript implementation to find the maximum number                       
                         // of chocolates to be distributed equally among                       
                         // k students                       
           
                         // function to find the maximum number of chocolates                       
                         // to be distributed equally among k students                       
                         function                                     maxNumOfChocolates(arr, n, k)                       
                         {                       
                                                 // unordered_map 'um' implemented as                       
                                                 // hash table                       
                                                 var                                     um =                                     new                                     Map();                       
           
                                                 // 'sum[]' to store cumulative sum, where                       
                                                 // sum[i] = sum(arr[0]+..arr[i])                       
                                                 var                                     sum = Array(n), curr_rem;                       
           
                                                 // to store sum of sub-array having maximum sum                       
                                                 var                                     maxSum = 0;                       
           
                                                 // building up 'sum[]'                       
                                                 sum[0] = arr[0];                       
                                                 for                                     (                                     var                                     i = 1; i < n; i++)                       
                                                 sum[i] = sum[i - 1] + arr[i];                       
           
                                                 // traversing 'sum[]'                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++) {                       
           
                                                 // finding current remainder                       
                                                 curr_rem = sum[i] % k;                       
           
                                                 // if true then sum(0..i) is divisible                       
                                                 // by k                       
                                                 if                                     (curr_rem == 0) {                       
                                                 // update 'maxSum'                       
                                                 if                                     (maxSum < sum[i])                       
                                                 maxSum = sum[i];                       
                                                 }                       
           
                                                 // if value 'curr_rem' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (!um.has(curr_rem))                       
                                                 um.set(curr_rem, i);                       
           
                                                 else                       
                                                 // if true, then update 'max'                       
                                                 if                                     (maxSum < (sum[i] - sum[um.get(curr_rem)]))                       
                                                 maxSum = sum[i] - sum[um.get(curr_rem)];                       
                                                 }                       
           
                                                 // required maximum number of chocolates to be                       
                                                 // distributed equally among 'k' students                       
                                                 return                                     (maxSum / k);                       
                         }                       
           
                         // Driver program to test above                       
                         var                                     arr = [2, 7, 6, 1, 4, 5];                       
                         var                                     n = arr.length;                       
                         var                                     k = 3;                       
                         document.write(                                     "Maximum number of chocolates: "                       
                                                 + maxNumOfChocolates(arr, n, k));                       
           
                         // This code is contributed by rutvik_56.                       
                         </script>                       

输出：

Maximum number of chocolates: 6

时间复杂性： O（n）。 辅助空间： O（n）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章