java - 如何在 k 个学生之间分配最多的巧克力

问题描述

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

给k个学生平均分配巧克力的最大数量
给定n 个盒子，里面有一些巧克力排列成一排。有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}。

我在 Geekforgeeks 中找到了解决方案——

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

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

标签： javaalgorithm

java - 如何在 k 个学生之间分配最多的巧克力

问题描述

解决方案

推荐阅读