Leetcode Solution-т хүмүүст чихэр тараана уу


Хэцүү байдлын түвшин Easy
Хоёртын хайлт Математик

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд хоёр тоо өгөгдсөн болно чихэр болон тооны_хүмүүс. Эхний тооны чихэр бол бидний байгаа чихрийн тоо юм. 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 (Brute Force)

Хамгийн энгийн арга бол эхний хүнд л чихэр өгч, 2-оос 2-р хүнд өгөх зэргээр сүүлчийн хүнд шилжүүлэх явдал юм. Дараа нь эхний хүн түүнд зохих ёсоор чихэр өгч эхэлнэ.
Үүнийг ашиглан хийж болно үүрлэсэн гогцоо, гаднах гогцоо нь үлдсэн чихэр байгаа нөхцөлд тохирох болно. Дотоод гогцоо нь зүүнээс баруун тийш гүйх бөгөөд байрлал бүрийн утгыг одоогийн чихэрээр нэгтгэнэ. Гэхдээ одоо үлдсэн чихэр нь одоогийн шаардлагаас бага байх нөхцөл байдал үүсч магадгүй юм. Тиймээс дотоод гогцоонд if else нөхцөл байдаг.

одоогоор шаардлагатай чихэр үлдсэн чихрээс их байх тохиолдолд үлдсэн чихрийг тухайн хүнд өгөх болно. Үгүй бол одоогийн шаардлагатай чихэрийг тухайн хүнд өгөх болно.

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 Solution-т хүмүүст чихэр тараах нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (max (sqrt (candies))): Одоогийн хэрэгцээ давталт бүрт нэгээр нэмэгдэж байна. Тиймээс чихрийн тоо эхлээд 1-ээр буурч, дараа нь 2-оор буурах гэх мэт.
Тиймээс t хугацааны дараа унасан чихрийн тоо t * (t + 1) / 2 буюу t хугацааны дараа t ^ 2 орчим чихэр унадаг.
Тиймээс c чихэр унагаахын тулд бидэнд sqrt (c) хугацаа хэрэгтэй болно.
Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь sqrt (чихэр) юм.

Сансрын нарийн төвөгтэй байдал 

O (тооны хүмүүс): Num_people хэмжээтэй массив ашиглаж байна. Тиймээс орон зайн нарийн төвөгтэй байдал нь O (тооны_хүмүүс) юм.

Хандлага 2 (Хоёртын хайлт)

Өмнөх арга барилд бид хүн бүрт нэг нэгээр нь чихэр өгч байсан. Дараа нь бид дахиад л мөчлөгөөр чихэр өгч эхэлнэ. Энэ бол мэдээж цаг хугацаа шаардсан үйл явц юм.
Тиймээс, энэ хандлагад бид дараахь алхамуудыг үндсэндээ хийх болно.

Нэгдүгээрт, бид чихрийн бүрэн гүйцэд биелэлтийг тооцоолно. өөрөөр хэлбэл бид дүрмийн дагуу яг нарийн чихэр авдаг хүмүүсийн тоог олох болно.
Тархалт 1-ээс эхэлж 1-ээр нэмэгдэх тул тархац нь 1 2 3 4 5 гэх мэт байх ёстой. Одоо бид 6 удаа чихэр амжилттай өгсөн гэж бодъё. Нийт хэрэглэсэн чихрийн тоо нь эхний 6 натурал тооны нийлбэр болно.
Тиймээс бид ямар ч үед хэрэглэсэн чихрийн тоо нь n натурал тооны нийлбэр бөгөөд n нь тухайн цаг хүртэл тархсан болохыг хэлж чадна.
Одоо бид дүрмийн дагуу хамгийн их амжилттай хуваарилалтыг хүсч байна. өөрөөр хэлбэл n-ийн хамгийн их утгыг n (n + 1) / 2 <= нийт чихрийн тоо байхаар хүсч байна.

N-ийн утгыг олж мэдэхийн тулд бидэнд олон арга хэрэглэдэг. Бид квадрат функцийг n-д шийдэж болно эсвэл n = 1 гэж эхэлж n-ийн утгыг n-ийн утга 1-ээр шугаман байдлаар орлуулж болно. Гэхдээ хамгийн зөв шийдэл бол энд хоёртын хайлтыг ашиглах явдал юм.

N-ийн утгыг олох хоёртын хайлт.

Хоёртын хайлтыг энд ашиглахын тулд n-ийн гарч болох хязгаарыг мэдэж байх ёстой. N-ийн хамгийн бага утга нь 1 байж болно гэж хэлж болно, учир нь чихрийн хязгаарлалт хамгийн багадаа 1 байна. Тиймээс бид дор хаяж 1 хүнд 1 чихэр өгөх боломжтой тул нэг амжилттай тараалтыг хийх хэрэгтэй (Тэгэхээр доод хязгаар l = 1000000). . N-ийн дээд хязгаарыг тооцоолоход төвөгтэй байж болох тул бид үүнийг өөртөө маш том бүхэл тоон утгыг өгөх болно (дээд хязгаар r = XNUMX байг).

Одоо бид l ба r хооронд тэгшитгэлийг хангах хамгийн их утга болох n цэгийг хүсч байна.
n (n + 1) / 2 <= нийт чихрийн тоо.
Хэрэв l ба r-ийн хооронд ямар нэг цэг (дунд цэгийг байг) дээрх тэгшитгэлийг хангаж байвал дараагийн цэг (өөрөөр хэлбэл дунд + 1) тэгшитгэлийг хангаж чадахгүй. Дараа нь дунд нь амжилттай тархалтын хамгийн их тоо байх болно.

Бид амжилттай хэрэгжсэн тоог (дунд) олсны дараа түгээлтийн бүрэн мөчлөгийн тоог хялбархан тооцоолох боломжтой бөгөөд энэ нь k = дунд /тооны_хүмүүс.

Одоо бид k бүтэн мөчлөг хийсний дараа хүн бүрт чихрийг тооцож байна.

Leetcode Solution-т хүмүүст чихэр тараана уу

 

Тиймээс бид k бүрэн мөчлөгийн дараа чихрийн тоог тооцоолох математик нэр томъёог оллоо. K + 1-р бүрэн бус мөчлөг яах вэ?
K + 1-р бүрэн бус мөчлөгт бид чихрийг амжилттай биелүүлэх нь nth хүмүүст хүрэхгүй, харин бидний чихэр хоорондоо дуусах болно гэж амархан хэлж чадна.

Бидний хамгийн сүүлийн амжилттай гүйцэтгэл дунд үе байна гэж аль хэдийн тооцоолсон. % Дундтооны_хүмүүс хүн эдгээр дунд чихрүүдийг авах болно. Дараагийн хүн үлдсэн бүх чихрийг авах болно.

Leetcode Solution-т хүмүүст чихэр тараана уу
Ийнхүү бид бүрэн бус мөчлөгийн сүүлийн хуваарилалтыг эхний дунд% -д нэмэх болнотооны_хүмүүс ба 1 + дунд%тооны_хүмүүс үлдсэн бүх чихэрийг авах болно.

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 Solution-т хүмүүст чихэр тараах нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (тооны хүмүүс):  Амжилттай биелсэн тоог олохын тулд бид хамгийн муу тохиолдолд 10 (ойролцоогоор) log (6 ^ 32) удаа ажиллуулах while циклийг ашиглаж байна. Тиймээс цаг хугацааны complextiy нь O (тооны_хүмүүс + 32) эсвэл O (тооны_хүмүүс) юм.

Тэмдэглэл: Энэ алгоритм нь чихрийн тоо хүмүүсийн тооноос хамаагүй их байх үед хамгийн сайн тохирох болно. Учир нь энэ алгоритм нь чихрийн тооноос хамаардаггүй.

Сансрын нарийн төвөгтэй байдал 

O (тооны хүмүүс): Num_people хэмжээтэй массив ашиглаж байна. Тиймээс орон зайн нарийн төвөгтэй байдал нь O (тооны_хүмүүс) юм.