Праверце, ці можа X змяніць кожнага чалавека ў чарзе


Узровень складанасці серада
Часта пытаюцца ў амазонка
чаргу

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

X - прадавец марожанага, і ў ёй чакаюць n чалавек чаргу купіць марожанае. Arr [i] абазначае намінал i-га чалавека ў чарзе, магчымыя значэнні наміналаў - 5, 10 і 20. Калі пачатковы баланс X роўны 0, а кошт марожанага - 5. Затым вызначыце, ці няма X зможаце змяніць усіх людзей, якія стаялі ў чарзе? Такім чынам, праблема заключаецца ў "Праверце, ці можа X змяніць кожнага чалавека ў чарзе".

Праверце, ці можа X змяніць кожнага чалавека ў чарзе

Прыкладаў

arr[] = {5, 5, 10, 20}
true
arr[] = {10, 5, 5, 5, 5, 5}
false
arr[] = {5, 5, 5, 20, 5, 10}
true

Алгарытм праверкі, ці можа X змяніць кожнага чалавека ў чарзе

Ідэя

Ідэя складаецца ў тым, каб сачыць за наміналамі 5, 10 і 20, якія ёсць у X. Няхай яны будуць прадстаўлены count5, count10 і count20. Заўсёды аптымальна вярнуць змены з як мага больш высокай коштам валюты. Усяго ёсць тры справы,

  • arr [i] = 5,
    павялічыць колькасць5 на 1
  • arr [i] = 10,
    Калі count5> 0, павялічце count10 на 1 і зменшыце count5 на 1
  • arr [i] = 20,
    Калі count10> 0 і count5> 0, павялічце count20 на 1, зменшыце count10 і count5 на 1.
    Інакш, калі count5> 2, павялічыць count20 на 1, зменшыць count5 на 3

Падыход

  1. Ініцыялізуйце тры зменныя count5, count10 і count20 як 0.
  2. Прайсці дадзенае масіў.
  3. Калі arr [i] роўны 5, павялічце count5 на 1.
  4. У адваротным выпадку, калі arr [i] роўны 10, праверце, калі count5> 0, калі так, павялічце count10 на 1 і зменшыце count5 на 1, інакш X не можа даць змены ўсім кліентам, вярнуць false.
  5. У адваротным выпадку, калі arr [i] роўны 20, праверце, калі count10 большы за 0, а count5 большы за 0. Калі так, павялічце count20 на 1 і зменшыце count5 і count10 на адзін, калі не, праверце, калі count5 большы за 2, калі так, павялічыць count20 на 1 і зменшыць count5 на 3, інакш X не можа даць змены ўсім кліентам, вярнуць false.
  6. Калі X змог вярнуць змены ўсім кліентам, вернеце true.

код

Код Java для праверкі, ці можа X змяніць кожнага чалавека ў чарзе

class CheckIfXCanGiveChangeToEveryPersonStandingInQueue {
    private static boolean checkIfPossible(int[] arr) {
        // initialize count0, counnt10 and count20 as 0
        int count5 = 0, count10 = 0, count20 = 0;
        
        // traverse in the array
        for (int i = 0; i < arr.length; i++) {
            // Case 1 : arr[i] = 5
            if (arr[i] == 5) {
                // increment count5 by 1
                count5++;
            }
            // Case 2 : arr[i] = 10
            else if (arr[i] == 10) {
                // if there are some 5 rs coins return 1
                if (count5 > 0) {
                    // decrement count5 by 1 and increment count10 by 1
                    count5--;
                    count10++;
                } else {
                    // if there are not, X cannot give change to everyone
                    return false;
                }
            }
            // Case 3 : arr[i] = 20
            else {
                // if there are some 10 rs coins and some 5 rs coin return one one each
                if (count10 > 0 && count5 > 0) {
                    count10--;
                    count5--;
                    count20++;
                } else if (count5 > 2) {
                    // else if there are 3 or more 5 rs coins return 3
                    count5 -= 3;
                    count20++;
                } else {
                    // X cannot give chnage to everyone
                    return false;
                }
            }
        }

        // X can give change to everyone
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 5, 10, 20};
        System.out.println(checkIfPossible(arr1));

        // Example 2
        int arr2[] = new int[] {10, 5, 5, 5, 5, 5};
        System.out.println(checkIfPossible(arr2));

        // Example 3
        int arr3[] = new int[]{5, 5, 5, 20, 5, 10};
        System.out.println(checkIfPossible(arr3));
    }
}
true
false
true

Код C ++ для праверкі, ці можа X змяніць кожнага чалавека ў чарзе

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

bool checkIfPossible(int *arr, int n) {
    // initialize count0, count10 and count20 as 0
    int count5 = 0, count10 = 0, count20 = 0;

    // traverse in the array
    for (int i = 0; i < n; i++) {
        // Case 1 : arr[i] = 5
        if (arr[i] == 5) {
            // increment count5 by 1
            count5++;
        }
        // Case 2 : arr[i] = 10
        else if (arr[i] == 10) {
            // if there are some 5 rs coins return 1
            if (count5 > 0) {
                // decrement count5 by 1 and increment count10 by 1
                count5--;
                count10++;
            } else {
                // if there are not, X cannot give change to everyone
                return false;
            }
        }
        // Case 3 : arr[i] = 20
        else {
            // if there are some 10 rs coins and some 5 rs coin return one one each
            if (count10 > 0 && count5 > 0) {
                count10--;
                count5--;
                count20++;
            } else if (count5 > 2) {
                // else if there are 3 or more 5 rs coins return 3
                count5 -= 3;
                count20++;
            } else {
                // X cannot give chnage to everyone
                return false;
            }
        }
    }

    // X can give change to everyone
    return true;
}

int main() {
    // Example 1
    int arr1[] = {5, 5, 10, 20};
    if (checkIfPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    int arr2[] = {10, 5, 5, 5, 5, 5};
    if (checkIfPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 3
    int arr3[] = {5, 5, 5, 20, 5, 10};
    if (checkIfPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
}
true
false
true

Аналіз складанасці

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

O (п), таму што мы прайшлі праз уваходны масіў, які мае n элементаў. І гэта прымусіла алгарытм працаваць у лінейны час.

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

O (1), таму што мы не выкарыстоўвалі масіў. Мы выкарыстоўваем donly 3 зменныя, якія займаюць пастаяннае месца. І такім чынам пастаянная касмічная складанасць.
дзе n - агульная колькасць кліентаў.