Կոնֆետներ բաժանեք մարդկանց Leetcode Solution


Դժվարության մակարդակ Հեշտ
Երկուական որոնում Մաթեմատիկա

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է երկու թիվ կոնֆետներ և num_people, Կոնֆետների առաջին համարը մեր ունեցած կոնֆետների քանակն է: num_people- ը ցույց է տալիս այն մարդու թիվը, որով մենք պետք է բաշխենք կոնֆետները:

Կոնֆետների բաշխման կանոնն է.
Մենք սկսում ենք ձախակողմյան անձից նրան տալ 1 կոնֆետ, ապա 2 կոնֆետ տալիս ենք 2-րդ անձին, 3 կոնֆետ 3-րդ անձին մինչև 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-րդ մարդուն և այսպես շարունակ տեղափոխվել վերջին մարդուն: Հետո նորից սկսեք առաջինից նրան համապատասխանաբար կոնֆետներ տալուց:
Դա կարելի է անել, օգտագործելով a տեղադրված հանգույց, որի արտաքին օղակը կաշխատի այն պայմանի համար, որը մնացել է քաղցրավենիք, թե ոչ: Ներքին օղակը կգործի ձախից աջ, որը կամփոփի յուրաքանչյուր դիրքի արժեքը տրվող կոնֆետների հետ: Բայց կարող է լինել մի իրավիճակ, երբ ներկայումս մնացած կոնֆետները փոքր կլինեն ներկայիս պահանջից: Այսպիսով, ներքին օղակում կա մի այլ իրավիճակ:

երբ ներկայումս պահանջվող կոնֆետներն ավելի մեծ են, քան մնացած կոնֆետները, մնացած կոնֆետները կտրվեն ընթացիկ անձին: Հակառակ դեպքում, ներկայիս պահանջվող կոնֆետները կտրվեն ընթացիկ անձին:

Իրականացում մարդկանց համար կոնֆետների բաշխման համար Leetcode Solution

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

Բարդության վերլուծություն մարդկանց համար կոնֆետներ բաշխելու համար Leetcode լուծում

Timeամանակի բարդություն

O (առավելագույն (sqrt (կոնֆետներ))): Ընթացիկ պահանջը յուրաքանչյուր օղակում ավելանում է մեկով: Այսպիսով, կոնֆետների քանակը նախ նվազում է 1-ով, ապա նվազում 2-ով և այլն:
Այսպիսով, t ժամանակից հետո ընկած կոնֆետների քանակը t * (t + 1) / 2 է, կամ t t.
Այսպիսով, c կոնֆետներ գցելու համար մեզ sqrt (c) ժամանակ է պետք:
Այսպիսով, ժամանակի բարդությունը sqrt (կոնֆետներ) է:

Տիեզերական բարդություն 

O (num_people): Օգտագործվում է num_people չափի զանգված: Այսպիսով, տիեզերական բարդությունը O է (num_people):

Մոտեցում 2 (Երկուական որոնում)

Նախորդ մոտեցմամբ մենք յուրաքանչյուրին հատ-հատ կոնֆետներ էինք տալիս: Հետո նորից մենք ի սկզբանե ցիկլիկորեն սկսում ենք կոնֆետներ տալ: Սա հաստատ ժամանակատար գործընթաց է:
Այսպիսով, այս մոտեցման մեջ մենք հիմնականում կատարելու ենք հետևյալ քայլերը:

Նախ, մենք հաշվարկում ենք կոնֆետների ամբողջական կատարման ընդհանուր քանակը: այսինքն `մենք կիմանանք այն մարդկանց ընդհանուր թվին, ովքեր ստացվում են ճշգրիտ կոնֆետներ` ըստ կանոնի:
Բաշխումը սկսվում է 1-ից և ավելանում 1-ով: Այսպիսով, բաշխումը պետք է լինի նման ՝ 1 2 3 4 5 6. Հիմա ենթադրենք, որ մենք հաջողությամբ 6 անգամ կոնֆետներ ենք տվել: Ապա սպառված ընդհանուր կոնֆետների քանակը առաջին 6 բնական թվերի գումարն է:
Այսպիսով, կարող ենք ասել, որ ցանկացած պահի սպառված կոնֆետների քանակը n բնական թվերի գումար է, որտեղ n- ը բաշխումն է, որը կատարվում է մինչև այդ ժամանակահատվածը:
Այժմ մենք ցանկանում ենք առավելագույն հաջող բաշխում ՝ ըստ կանոնի: այսինքն մենք ուզում ենք n- ի առավելագույն արժեքն այնպես, որ n (n + 1) / 2 <= կոնֆետների ընդհանուր քանակը:

N- ի արժեքը պարզելու համար մենք ունենք բազմաթիվ մոտեցումներ: Մենք կարող ենք լուծել քառակուսային ֆունկցիան n- ի համար կամ կարող ենք սկսել n = 1-ը և շարունակել փոխարինել n- ի արժեքը 1-ով n աճող արժեքով գծային: Բայց ամենահարմար լուծումը այստեղ երկուական որոնումն օգտագործելն է:

Երկուական որոնում ՝ n- ի արժեքը գտնելու համար:

Երկուական որոնումն այստեղ օգտագործելու համար մենք պետք է իմանանք այն սահմանը, որի մեջ կարող է n լինել: Կարող ենք ասել, որ գոնե n արժեքը կարող է լինել 1, որովհետև կոնֆետների կաշկանդվածությունը առնվազն 1 է: Այսպիսով, մենք կարող ենք գոնե 1 կոնֆետ տալ առաջին դեմքին ՝ այդպիսով կատարելով մեկ հաջող բաշխում (Այսպիսով, ստորին սահմանը l = 1) , N- ի վերին սահմանը կարող է բարդ լինել հաշվարկելու համար, ուստի մենք պարզապես մեր ինքնուրույն դրան տալիս ենք շատ մեծ ամբողջ թիվ (թող վերին սահմանը r = 1000000):

Այժմ մենք ուզում ենք n և r կետերի միջև կետ, որը առավելագույն արժեքն է, որը բավարարում է հավասարումը:
n (n + 1) / 2 <= կոնֆետների ընդհանուր քանակը:
Եթե ​​l- ի և r- ի միջև որևէ կետ (թող կետը միջին լինի) բավարարում է վերը նշված հավասարումը: և հաջորդ կետը (այսինքն ՝ կես + 1) չի կարող բավարարել հավասարումը: Այդ ժամանակ կեսը կլինի հաջող բաշխման առավելագույն քանակը:

Այն բանից հետո, երբ մենք գտել ենք հաջող կատարումների քանակը (միջին), մենք հեշտությամբ կարող ենք հաշվարկել բաշխման ամբողջական ցիկլերի քանակը, որը k = կես /num_people.

Այժմ մենք հաշվարկում ենք կոնֆետները յուրաքանչյուր անձի համար k ամբողջական ցիկլերից հետո:

Կոնֆետներ բաժանեք մարդկանց Leetcode Solution

 

Այսպիսով, մենք գտել ենք մաթեմատիկական տերմիններ k ամբողջական ցիկլերից հետո կոնֆետների քանակը հաշվարկելու համար: Ինչ վերաբերում է k + 1-ին թերի ցիկլին:
K + 1-ին թերի ցիկլում մենք հեշտությամբ կարող ենք ասել, որ քաղցրավենիքի հաջող կատարումը չի գնա իններորդ մարդկանց, մեր կոնֆետները կավարտվեն արանքում:

Մենք արդեն հաշվարկել ենք, որ մեր վերջին հաջող կատարումը կեսն է: Իսկ միջին%num_people մարդը կվերցնի այդ կեսերի կոնֆետները: Եվ հաջորդ մարդը կստանա մնացած բոլոր կոնֆետները:

Կոնֆետներ բաժանեք մարդկանց Leetcode Solution
Այսպիսով, մենք կավելացնենք այս վերջին ոչ լրիվ ցիկլի բաշխումը մեր առաջին միջին% -ինnum_people և 1 + միջին%num_people կստանան մնացած բոլոր կոնֆետները:

Իրականացում մարդկանց համար կոնֆետների բաշխման համար Leetcode Solution

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

Բարդության վերլուծություն մարդկանց համար կոնֆետներ բաշխելու համար Leetcode լուծում

Timeամանակի բարդություն

O (num_people):  Հաջող կատարման քանակը գտնելու համար մենք օգտագործում ենք մի ժամանակաշրջան, որն աշխատելու է գրանցման (10 ^ 6) անգամ վատագույն դեպքում, որը կազմում է մոտ 32: Այնուհետև մենք գործարկել ենք մի օղակ գծային թվով մարդկանց անգամ: Այսպիսով, ժամանակի բարդությունը O է (num_people + 32) կամ O (num_people):

Նշում. Այս ալգորիթմը լավագույնը կլինի, երբ կոնֆետների քանակը շատ ավելին է, քան մարդկանց քանակը: Քանի որ, այս ալգորիթմը կախված չէ կոնֆետների քանակից:

Տիեզերական բարդություն 

O (num_people): Օգտագործվում է num_people չափի զանգված: Այսպիսով, տիեզերական բարդությունը O է (num_people):