如何在k学生中最大限度地分发巧克力

Question

我在一次采访中被问到这个问题-

如果n个盒子中有一些巧克力排成一行，则在k名学生中平均分配的巧克力最大数量
。有k个学生。问题是通过从给定批次中选择一系列连续的盒子，在k个学生中平均分配最大数量的巧克力。假设这些框按从左到右从1到n的数字排成一行。我们必须选择一组连续排列的盒子，以便为所有k学生提供最多数量的巧克力。给出了一个数组arr[]，表示盒子的行排列，arr[i]表示盒子中位置i处的巧克力数量。

示例：

输入：arr[]={2，7，6，1，4，5}，k=3
输出：6
子阵列为{7，6，1，4}，和18<18块巧克力在3名学生中的平均分配是6块<请注意，所选框按索引{1、2、3、4}的连续顺序排列。

我在GeekForgeks中找到了解决方案--

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); 
} 

这行得通，但我需要一些解释为什么行得通，我能理解这个部分--

 if (curr_rem == 0) { 
           // update 'maxSum' 
           if (maxSum < sum[i]) 
               maxSum = sum[i]; 
       } 

如果数组元素的连续和可被k整除，则会起作用，但请尝试理解这一部分--

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)];

这里的任何解释都会很有帮助

Answer 1

class Solve
{
//arr -> chocolates values, n = len(arr), k->no of students
//Idea:
//1.to use prefix sum and find the subarray whose sum is divisible by k.
//2.when we find the subarray we try to find the sum of this subarray by using 
//precomputation sum of arr
//3.we keep a max variable to record the max sum and return max that's it!!!!!
    static int maxNumOfChocolates(int arr[], int n, int k) 
    { 
        if(n==0)return 0;
        int []prefix = new int[n];
        prefix[0] = arr[0];
        for(int i=1;i<n;++i){
            prefix[i] = prefix[i-1]+arr[i];
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int ans = -1;
        int sum = 0;
        for(int i=0;i<n;i++){
            sum+=arr[i];
            if(map.containsKey(sum%k)){
                int j = map.get(sum%k);
                ans = Math.max(ans,prefix[i]-((j>=0)?prefix[j]:0));
            }
            map.putIfAbsent(sum%k,i);
        }
        if(ans==-1)return -1;
        return ans/k;
    } 

}

Answer 2

非常简短的解释：

在主循环中，查看从索引0到当前索引的所有和。如果有余数，则必须检查是否可以从0以外的其他索引开始“使其消失”。

检查这与查找之前存储的相等余数完全相同。

例如，您在索引7处有余数3。如果您在索引13处再次有余数3，则在7和13之间相加就没有余数。剩下的是取最大值。找到的所有解决方案的总和。