사탕 Leetcode 솔루션의 가장 많은 수를 가진 아이들-TutorialCup

“가장 많은 사탕을 가진 아이들”문제에서 우리는 어떤 아이들이 가지고있는 초콜릿의 수를 나타내는 정수 배열과 어떤 식 으로든 배포 할 수있는 추가 사탕을 제공받습니다. 이제 다음을 찾아야합니다.

모든 어린이가 가장 많은 수의 초콜릿을 가질 수 있습니까? 배포 후(과반수 또는 공동)?

이 가능성을 부울 벡터의 형태로 출력해야합니다.

차례

예

Array = {1 , 4 , 5 , 6 , 7}
Extra = 5

false true true true true

설명

첫 번째 아이: 다 줘도 5 첫 번째 자녀에게 추가 사탕, 6 개 미만의 사탕 <7 (5 번째 자녀). 그래서 우리는 그릇된 그것을 위해.

둘째 아이: 우리는 모두를 5 이 아이에게 추가 사탕을 9 > 7 (다섯 번째 자녀). 그래서 우리는 참된 그것을 위해.

마찬가지로, 세 번째, 네 번째, 다섯 번째 아이의 경우 최적의 분배 후 가장 많은 수의 사탕을 가질 수 있음을 쉽게 알 수 있습니다.

접근 (Greedy)

문제에서 우리는 여분의 사탕을 배포하기위한 우리의 선택과 무관합니다. 그만큼 최적의 어떤 아이를 위해 결정하는 방법은 여분의 사탕을 모두주고 필요한 상태를 확인하는 것입니다. 고려할 사항에 대한 결과를 찾아야합니다. i 번째 아이. 이제, 그것에 줄 수있는 사탕의 최대 양은 총 추가 사탕과 같습니다.

따라서 소유 할 수있는 사탕의 총 수는 i 번째 child = a [i] + 추가 사탕. 이 값이 최대 요소보다 큰 경우 정렬 분배하기 전에 우리는이 아이가 분배 후 가장 많은 사탕을 가질 수 있다는 결론을 내릴 수 있습니다. 우리는 모든 여분의 사탕을 i 번째 이 접근 방식은 탐욕스러운.

핀

암호알고리즘

배열의 최대 값을 찾아서 다음과 같이 저장하십시오. 맥스캔디
부울 초기화 결과 정렬
배열의 시작부터 끝까지 루프를 실행합니다.
1. 현재 사탕 수가 i 번째 어린이 + 추가 사탕은 이상인 maxCandies :
  1. 이 자식의 결과를 다음과 같이 설정하십시오. 참된, 그릇된 그렇지 않으면
결과 인쇄

사탕 수가 가장 많은 어린이를 찾기위한 알고리즘 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

vector <bool> kidsWithCandies(vector <int> &candies , int extraCandies)
{
    int n = candies.size() , maxCandies = 0;
    for(int i = 0 ; i < n ; i++)
        if(candies[i] > maxCandies)
            maxCandies = candies[i];


    vector <bool> result(n);
    for(int i = 0 ; i < n ; i++)
        result[i] = (candies[i] + extraCandies >= maxCandies);

    return result;
}


int main()
{
    vector <int> candies = {1 , 4 , 5 , 6 , 7};
    int extraCandies = 5;
    for(bool x : kidsWithCandies(candies , extraCandies))
        cout << (x ? "true" : "false") << " ";
    cout << '\n';
    return 0;
}

자바 프로그램

class kids_with_candies
{
    public static void main(String args[])
    {
        int[] candies = {1 , 4 , 5 , 6 , 7};
        int extraCandies = 5;
        for(boolean x : kidsWithCandies(candies , extraCandies))
            System.out.print(x + " ");
    }


    static boolean[] kidsWithCandies(int[] candies , int extraCandies)
    {
        int n = candies.length , maxCandies = 0;
        for(int i = 0 ; i < n ; i++)
            if(candies[i] > maxCandies)
                maxCandies = candies[i];

        boolean[] result = new boolean[n];

        for(int i = 0 ; i < n ; i++)
            result[i] = (candies[i] + extraCandies >= maxCandies);

        return result;
    }
}

false true true true true

가장 많은 사탕을 가진 아이를 찾는 복잡성 분석

시간 복잡성

의 위에), N = 배열의 크기. 전체 배열을 한 번 횡단하면서.

공간 복잡성

의 위에), 모든 자식의 결과를 별도의 배열에 저장합니다.

Twitter Facebook 링크드 인 버퍼 레딧 텀블러

가장 많은 수의 캔디를 가진 아이들 Leetcode 솔루션

예

설명