Раздайце людзям цукеркі


Узровень складанасці Лёгка
Двайковы пошук Матэматыка

Пастаноўка праблемы

У гэтай задачы нам дадзены два нумары цукеркі і колькасць_людзей. Цукеркі першага ліку - гэта колькасць цукерак, якія мы маем. num_people паказвае колькасць людзей, у якіх мы павінны раздаваць цукеркі.

Правіла распаўсюджвання цукерак:
Мы пачынаем з самага левага чалавека, даем яму 1 цукерку, потым даем 2 цукеркі 2-й асобе, 3 цукеркі 3-й асобе да n цукерак n-й асобе. Пасля гэтага мы зноў пачынаем з самага левага чалавека, даючы яму n + 1 цукеркі, потым n + 2, n + 3. Гэта цыклічнае размеркаванне працягваецца да таго часу, пакуль у нас не скончыцца цукерак, гэта значыць, калі нашы астатнія цукеркі будуць ніжэйшыя за патрэбныя, мы аддамо астатнія цукеркі цяперашняму чалавеку, а потым спынімся.

Прыклад

candies = 7, num_people = 4
[1,2,3,1]

Тлумачэнне:

На першым павароце ans [0] + = 1, а масіў [1,0,0,0].
На другім павароце ans [1] + = 2, і масіў [1,2,0,0].
Трэці ход, ans [2] + = 3, і масіў [1,2,3,0].
Чацвёрты ход, ans [3] + = 1 (бо засталася толькі адна цукерка), а канчатковы масіў - [1,2,3,1].

candies = 10, num_people = 3
[5,2,3]

Тлумачэнне:

На першым павароце ans [0] + = 1, а масіў [1,0,0].
На другім павароце ans [1] + = 2, і масіў [1,2,0].
Трэці ход, ans [2] + = 3, і масіў [1,2,3].
Чацвёрты ход, ans [0] + = 4, і канчатковы масіў [5,2,3].

Падыход 1 (грубая сіла)

Самы просты падыход - даць л цукеркі першай асобе, а 2 - 2-й асобе і гэтак далей перайсці да апошняй асобы. Затым зноў пачніце ад першага, хто дасць яму цукеркі адпаведна.
Гэта можа быць зроблена з дапамогай укладзеная пятля, пры якім знешняя пятля будзе працаваць пры ўмове, што засталіся цукеркі ці не. Унутраная пятля будзе працаваць злева направа, што будзе падводзіць значэнні кожнай пазіцыі з бягучымі цукеркамі. Але можа быць сітуацыя, калі цукеркі, якія засталіся ў цяперашні час, будуць меншыя, чым цяперашнія патрабаванні. Такім чынам, ва ўнутраным цыкле ёсць умова if else.

калі ў цяперашні час неабходныя цукеркі перавышаюць астатнія цукеркі, астатнія цукеркі перададуць бягучаму чалавеку. У адваротным выпадку бягучыя неабходныя цукеркі будуць перададзены бягучаму чалавеку.

Рэалізацыя рашэння Leetcode для распаўсюджвання цукерак сярод людзей

Праграма C ++

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        vector<int>ans;
        /*
        initially everyone has no candy. Thus, answer array is filled up with zeros.
        */
        for(int i=0;i<num_people;i++){
            ans.push_back(0);
        }
        int cur=0;//current requirement is initialized to zero
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++; //current requirement increments by one each time.
                if(candies>=cur){ //checks if the remaining candies are greater than current requirement 
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

Праграма Java

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
        int[]ans=new int[num_people];
        Arrays.fill(ans,0);
        int cur=0;
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++;
                if(candies>=cur){
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
}
5 2 3

Аналіз складанасці для распаўсюджвання цукерак сярод людзей

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

O (макс. (Sqrt (цукеркі))): Патрабаванні да бягучага ўзрастаюць на адзін у кожным цыкле. Такім чынам, колькасць цукерак спачатку памяншаецца на 1, потым памяншаецца на 2 і гэтак далей.
Такім чынам, праз час t колькасць цукерак, якія ўпалі, складае t * (t + 1) / 2 альбо прыблізна t ^ 2 цукеркі падаюць праз час t.
Такім чынам, каб кінуць цукеркі, нам патрэбны час sqrt (c).
Такім чынам, складанасць часу складае sqrt (цукеркі).

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

O (колькасць чалавек): Выкарыстоўваецца масіў памерам num_people. Такім чынам, касмічная складанасць складае O (колькасць_людзей).

Падыход 2 (Двайковы пошук)

У папярэднім падыходзе мы давалі цукеркі кожнаму па чарзе. Потым зноў цыклічна пачынаем даваць цукеркі з самага пачатку. Гэта, безумоўна, працаёмкі працэс.
Такім чынам, пры гэтым падыходзе мы ў асноўным выканаем наступныя этапы.

Па-першае, мы разлічваем агульную колькасць поўнага выканання цукерак. г.зн. мы даведаемся агульную колькасць людзей, якія атрымліваюць дакладныя цукеркі ў адпаведнасці з правіламі.
Размеркаванне пачынаецца з 1 і павялічваецца на 1. Такім чынам, размеркаванне павінна быць прыблізна 1 2 3 4 5 6. Зараз выкажам здагадку, што мы цудоўна далі цукеркі 6 разоў. Тады колькасць агульных спажываных цукерак складае першыя 6 натуральных лічбаў.
Такім чынам, мы можам сказаць, што ў любы момант часу колькасць спажываных цукерак з'яўляецца сумай n натуральных лікаў, дзе n - размеркаванне, праведзенае да гэтага моманту.
Цяпер мы хочам максімальна паспяховага размеркавання ў адпаведнасці з правілам. г.зн. мы хочам, каб максімальнае значэнне n было такім, каб n (n + 1) / 2 <= агульная колькасць цукерак.

Для высвятлення значэння n у нас ёсць некалькі падыходаў. Мы можам вырашыць квадратычную функцыю для n альбо мы можам пачаць з n = 1 і працягваць падмяняць значэнне n з павелічэннем значэння n на 1 лінейна. Але найбольш прыдатным рашэннем з'яўляецца выкарыстанне бінарнага пошуку тут.

Бінарны пошук, каб знайсці значэнне n.

Каб выкарыстоўваць тут бінарны пошук, мы павінны ведаць, у якой мяжы можа прыйсці n. Мы можам сказаць, што па меншай меры значэнне n можа быць 1, таму што абмежаванне цукерак складае па меншай меры 1. Такім чынам, мы можам даць па меншай меры 1 цукерку першаму чалавеку, таму зрабіць адно паспяховае размеркаванне (Такім чынам, ніжняя мяжа l = 1) . Верхняя мяжа п можа быць складана вылічыць, таму мы проста надаём ёй вельмі вялікае цэлае значэнне самастойна (няхай верхняя мяжа r = 1000000).

Цяпер мы хочам кропку n паміж l і r, якая з'яўляецца максімальным значэннем, якое задавальняе ўраўненню.
n (n + 1) / 2 <= агульная колькасць цукерак.
Калі любая кропка (няхай кропка ў сярэдзіне) паміж l і r задавальняе вышэйапісанаму ўраўненню. і наступны пункт (г.зн. сярэдзіна + 1) не можа задаволіць раўнанне. Тады сярэдзіна будзе максімальнай колькасцю паспяховага размеркавання.

Пасля таго, як мы знайшлі колькасць паспяховых выкананняў (сярэдзіна), мы можам лёгка вылічыць колькасць поўных цыклаў размеркавання, якое складае k = сярэдзіна /колькасць_людзей.

Цяпер мы разлічваем цукеркі кожнаму чалавеку пасля k поўнага цыкла.

Раздайце людзям цукеркі

 

Такім чынам, мы знайшлі матэматычныя тэрміны для разліку колькасці цукерак пасля k поўнага цыкла. А як наконт k + 1-га няпоўнага цыкла.
У k + 1-м няпоўным цыкле можна лёгка сказаць, што паспяховае выкананне цукерак не пойдзе ні на каго, а нашы цукеркі будуць скончаны дзесьці паміж імі.

Мы ўжо падлічылі, што наша апошняе паспяховае выкананне - сярэдзіна. І сярэдзіна%колькасць_людзей чалавек будзе прымаць гэтыя цукеркі ў сярэдзіне. А наступны чалавек атрымае ўсе цукеркі, якія засталіся.

Раздайце людзям цукеркі
Такім чынам, мы дадамо гэты апошні няпоўны размеркаванне цыкла да нашага першага сярэдняга%колькасць_людзей і 1 + сярэдзіна%колькасць_людзей атрымаюць усе астатнія цукеркі.

Рэалізацыя рашэння Leetcode для распаўсюджвання цукерак сярод людзей

Праграма C ++

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long ans[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person 
        vector<int> ans1;
        for(i=0;i<num_people;i++){
            ans1.push_back((int)(ans[i]));
        }
        return ans1;
        
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

Праграма Java

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
       
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long[]ans=new long[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person
        int[]ans1=new int[num_people];
        for(i=0;i<ans1.length;i++){
            ans1[i]=(int)(ans[i]);
        }
        return ans1;
    }
}
5 2 3

Аналіз складанасці для распаўсюджвання цукерак сярод людзей

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

O (колькасць чалавек):  Каб знайсці колькасць паспяховых выкананняў, мы выкарыстоўваем цыкл while, які будзе працаваць для часопіса (10 ^ 6) разоў, у горшым выпадку каля 32. Тады мы запусцілі цыкл лінейна num_people раз. Такім чынам, складанасць часу складае O (колькасць_людзей + 32) або O (колькасць_людзей).

Заўвага: Гэты алгарытм будзе лепшым, калі колькасць цукерак значна большая, чым колькасць людзей. Таму што гэты алгарытм не залежыць ад колькасці цукерак.

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

O (колькасць чалавек): Выкарыстоўваецца масіў памерам num_people. Такім чынам, касмічная складанасць складае O (колькасць_людзей).