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


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны
дараалал

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

X бол зайрмагны худалдагч бөгөөд а-г хүлээж байгаа n хүн байна дараалал зайрмаг худалдаж авах. Arr [i] нь дараалалд байгаа хүний ​​нэрлэсэн утгыг илэрхийлнэ. Мөнгөн тэмдэгтийн боломжит утга 5, 10 ба 20 бол X-ийн анхны үлдэгдэл 0 ба зайрмагны өртөг 5 бол X-ийг тодорхойлно уу. дараалалд зогсож буй бүх хүмүүст өөрчлөлт өгөх боломжтой юу? Тиймээс асуудал нь "Х дараалалд байгаа бүх хүнд өөрчлөлт өгч чадах эсэхийг шалгах" явдал юм.

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

жишээ нь

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

X нь дараалалд байгаа бүх хүнд өөрчлөлт өгч чадах эсэхийг шалгах алгоритм

санаа

Энэ санаа нь X-тэй 5, 10, 20-ийн гүйлгээний тэмдэглэл хөтлөх явдал юм. Эдгээрийг 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 бол тоолох тоолол> 5 байгаа эсэхийг шалгана уу, тийм бол тооллыг 0-аар 10-ээр, тоог 1-аас 5-ээр бууруул, тэгэхгүй бол X бүх үйлчлүүлэгчдэд өөрчлөлт өгч чадахгүй, худал гэж буцаана.
  5. Хэрэв arr [i] нь 20 бол тоолох тоо 10-ээс их, count0 нь 5-ээс их байгаа эсэхийг шалгана уу. Тийм бол count0-ийг 20-ээр нэмэгдүүлж, count1-ийг бууруулж, count5-ийг нэгээр нэм, хэрэв үгүй ​​бол count10 5-оос их эсэхийг шалгана. Тийм ээ, тоог 2-оор 20-ээр, 1-ыг 5-аар бууруулж, өөрөөр хэлбэл X нь бүх үйлчлүүлэгчдэд өөрчлөлт өгч чадахгүй, худал гэсэн утгатай.
  6. Хэрэв X бүх үйлчлүүлэгчдэд өөрчлөлтийг буцааж өгч чадсан бол үнэнийг буцаана.

код

X нь дараалалд байгаа бүх хүнд өөрчлөлт өгч чадах эсэхийг шалгах Java код

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

X нь дараалалд байгаа бүх хүнд өөрчлөлт өгч чадах эсэхийг шалгах C ++ код

#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), Учир нь бид n элемент бүхий оролтын массивыг туулсан. Энэ нь алгоритмыг шугаман хугацаанд ажиллуулах боломжийг олгов.

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

O (1), Учир нь бид ямар ч массив хэрэглээгүй. Бид байнгын зай эзэлдэг donly 3 хувьсагчийг ашигладаг. Тиймээс орон зайн нарийн төвөгтэй байдал.
энд n нь нийт үйлчлүүлэгчдийн тоо юм.