在k名學生中平均分配的最大巧克力數量


難度級別
經常問 埃森哲 土磚 亞馬遜 Facebook 風箏
排列 哈希

“在k個學生中平均分配的最大巧克力數量”指出,您將得到n個裝有巧克力的盒子。 假設有k個學生。 任務是通過選擇連續的盒子,在k個學生之間平均分配最大數量的巧克力。 我們可以假設框在由1到n的數字組成的行中。 任務是選擇一組可以將最多數量的巧克力平均分配給k個學生的盒子。 給出的框可以視為一個數組,並且arr [i]可以表示在第i個索引位置處其中的巧克力數量。

arr[] = {1, 5, 3, 6, 10, 1}

k = 3
8

說明: 子數組5、3、6、10中的數字構成24個巧克力,可以分配給k個學生。 這意味著每個學生8塊巧克力,這是給定值的最大值。

算法

1. Declare a map.
2. Declare an array ‘sum’ of size n (length of the given array).
3. Set resultant to 0 and copy the value of arr[0] to sum[0].
4. Add all the values of arr[i] and sum[i-1] and store each value at sum[i].
5. Traverse the array, while i < n (length of the array).
  1. Set temp to sum[i]%k and check if the temp is equal to 0.
    1. If true then check for if resultant is less than sum[i], if true, then update resultant = sum[i].
  2. Check if the temp is present in a map, if present, then, push this value and the current index into the map.
  3. Else get the number which is related with the temp in a map, let x= map[temp], check if resultant is less than the sum[i] –sum[x].
    1. If true then update the value of resultant=sum[i]-sum[x], where x is map[temp].
6. Return the (resultant / k ).

解釋

我們已經完成了一項任務,即在k名學生中平均分配最多的巧克力。 該框基本上是代表巧克力數量的數組。 還有一個條件,我們必須選擇連續的盒子來分配巧克力,並且分配應該最大化。

我們將使用 散列。 我們將聲明一個 地圖。 但是,在此之前,我們將創建一個空數組,該數組的大小與給定數組的大小相同,即n。 將值sum [0]設置為arr [0],意味著sum [0]的第一個值應與arr [0]相同。 遍歷 排列,我們將把arr [i]和sum [i-1]相加並將其值存儲到sum [i]中,這樣,我們將把一個數組的值與sum的前一個indexs元素相加。 我們將在sum數組中包含值。

讓我們舉一個例子:

arr [] = {1,5,3,6,10,1},k = 3

sum [0] = arr [0] = 1。

sum [1] = arr [i] + sum [i-1] = 6,

sum [2] = arr [i] + sum [i-1] = 9,繼續進行下去,我們將在sum數組中具有以下值。

sum [] = {1、6、9、15、25、26}。

我們將再次遍歷數組,將溫度作為和[i]%k。 我們將檢查temp是否等於0,但不等於1,0,因此我們將檢查映射是否不包含該值,我們會將其與當前索引一起放入映射中。 所以在地圖上,我們現在有(XNUMX)。

拾取下一個數字6並檢查sum [i]%k作為溫度,現在發現它為0,所以我們現在將更新結果。 結果將是6。

下一個元素是9和15,在此模式中,兩個模的模數均為3,因此最多0,結果將為15。下一個數字是15,我們現在的溫度為25。到其他條件。 但是我們已經有1個進入了地圖。 因此,當我們將1和0存儲到映射中時,我們將得到它的值,即1。 然後,我們將得出sum [i] -sum [0],即0,將結果更新為該數字。

再訪問一個數字後,我們仍然會得到24的答案。最後,我們將返回24/3(即8)。這將是我們的最終答案。

在k名學生中平均分配的最大巧克力數量

履行

C ++程序,可在k個學生之間平均分配最大數量的巧克力

#include<iostream>
#include<unordered_map>

using namespace std;

int getChocolateNumbers(int arr[], int n, int k)
{
    unordered_map<int, int> MAP;

    int sum[n];

    int resultant = 0;

    sum[0] = arr[0];
    for (int i = 1; i < n; i++)
        sum[i] = sum[i - 1] + arr[i];

    for (int i = 0; i < n; i++)
    {
        int temp = sum[i] % k;

        if (temp == 0)
        {
            if (resultant < sum[i])
                resultant = sum[i];
        }
        else if (MAP.find(temp) == MAP.end())
            MAP[temp] = i;

        else if (resultant < (sum[i] - sum[MAP[temp]]))
            resultant = sum[i] - sum[MAP[temp]];
    }
    return (resultant / k);
}
int main()
{
    int arr[] = {1, 5, 3, 6, 10, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Number of chocolates which can be equally distributed:  "<< getChocolateNumbers(arr, n, k);
    return 0;
}
Number of chocolates which can be equally distributed:  8

Java程序,可在k個學生中平均分配最大數量的巧克力

import java.util.HashMap;

class distributionOfChocolates
{
    public static int getChocolateNumbers(int arr[], int n, int k)
    {
        HashMap <Integer,Integer> MAP = new HashMap<Integer,Integer>();

        int sum[]=new int[n];

        int resultant = 0;

        sum[0] = arr[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] = sum[i - 1] + arr[i];
        }
        for (int i = 0; i < n; i++)
        {
            int temp = sum[i] % k;

            if (temp == 0)
            {
                if (resultant < sum[i])
                    resultant = sum[i];
            }

            else if (!MAP.containsKey(temp) )
                MAP.put(temp, i);

            else if (resultant < (sum[i] - sum[MAP.get(temp)]))
                resultant = sum[i] - sum[MAP.get(temp)];
        }

        return (resultant / k);
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,5,3,6,10,1 };
        int n = arr.length;
        int k = 3;
        System.out.println("Number of chocolates which can be equally distributed: "+ getChocolateNumbers(arr, n, k));
    }
}
Number of chocolates which can be equally distributed: 8

在k個學生中平均分配巧克力的最大數量的複雜性分析

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。

參考文獻