Максімальная колькасць шакаладных цукерак, якія будуць аднолькава размеркаваны паміж k студэнтамі


Узровень складанасці серада
Часта пытаюцца ў Accenture Саман амазонка facebook Фуркайты
масіў гашыш

"Максімальная колькасць шакаладных цукерак, якія трэба размеркаваць пароўну паміж k студэнтамі", сведчыць, што вам даецца n скрынак, у якіх ёсць некалькі цукерак. Дапусцім, ёсць k студэнтаў. Задача - размеркаваць максімальную колькасць шакаладных цукерак паміж k студэнтамі пароўну, выбраўшы паслядоўныя скрынкі. Мы можам выказаць здагадку, што скрынкі знаходзяцца ў шэраг, які складаецца з лікаў ад 1 да n. задача складаецца ў тым, каб выбраць групу каробак, якія могуць аднолькава размеркаваць найбольшую колькасць шакаладных цукерак. Прыведзеныя скрынкі можна разглядаць як масіў, а 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. Усталюйце значэнне [0] як arr [0], азначае, што першае значэнне [0] павінна быць такім жа, як arr [0]. Пры праходжанні масіў, мы будзем дадаваць arr [i] і sum [i-1] і захоўваць значэнне ў sum [i], такім чынам, мы будзем складаць значэнні масіва і папярэдняга элемента індэкса sum. Мы будзем мець значэнні ў гэтым масіве sum.

Возьмем прыклад гэтага:

Прыклад

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

сума [0] = arr [0] = 1.

сума [1] = arr [i] + сума [i-1] = 6,

sum [2] = arr [i] + sum [i-1] = 9, працягваючы яго, мы будзем мець наступныя значэнні ў масіве sum.

сума [] = {1, 6, 9, 15, 25, 26}.

Мы зноў пройдзем масіў, падбіраючы temp як sum [i]% k. Мы праверым, ці адпавядае тэмпература 0, але гэта не так, таму мы праверым, калі карта не ўтрымлівае гэтага значэння, мы паставім яе з бягучым індэксам на карту. Такім чынам, на карце мы маем (1,0) зараз.

Падбіраючы наступны нумар 6 і правяраючы суму [i]% k як тэмпературу, зараз выяўляецца 0, таму мы абнавім выніковую зараз. У выніку атрымаецца 6.

Наступны элемент будзе 9 і 15, у гэтым шаблоне абодва маюць па сутнасці 3 роўныя 0, таму да 15 выніковая будзе 15. Наступная лічба 25, у нас цяпер тэмп як 1. Такім чынам, мы будзем пераходзіць да іншага стану. Але мы маем 1 ужо на карце. Такім чынам, мы атрымаем яго значэнне, якое складае 0, бо мы захавалі 1 і 0 на карце. Тады мы даведаемся суму [i] -суму [0], і гэта будзе 24, выніковае абнаўленне да гэтага ліку.

Наведаўшы яшчэ адзін нумар, у нас усё яшчэ ёсць адказ: 24. Нарэшце, мы вернемся 24/3, гэта значыць 8. Гэта будзе наш канчатковы адказ.

Максімальная колькасць шакаладных цукерак, якія будуць аднолькава размеркаваны паміж k студэнтамі

Рэалізацыя

Праграма C ++ для максімальнай колькасці шакаладных цукерак, якія будуць раўнамерна размеркаваны паміж студэнтамі

#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

Аналіз складанасці максімальнай колькасці шакаладных цукерак, якія будуць аднолькава размеркаваны сярод студэнтаў

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве.

Спасылка