การนำออกสูงสุดจากอาร์เรย์เมื่อเวลานำออก ≥ เวลารอใน C++

บทนำ

ในปัญหานี้ เราได้รับอาร์เรย์ N องค์ประกอบ ภารกิจคือหาจำนวนการนำออกสูงสุดจากอาร์เรย์เมื่อเวลานำออก (Removal Time) มากกว่าหรือเท่ากับเวลารอ (Waiting Time)

เราจะนำองค์ประกอบของอาร์เรย์ออก ค่าขององค์ประกอบแทนเวลานำออก (เวลาที่ใช้ในการนำองค์ประกอบนั้นออกจากอาร์เรย์)

องค์ประกอบมีเวลารอ คือเวลาที่ต้องรอจนกว่าจะได้ถูกนำออก

องค์ประกอบสามารถนำออกได้ก็ต่อเมื่อ เวลานำออกมากกว่าหรือเท่ากับเวลาที่ต้องรอ

เราต้องหาจำนวนสูงสุดขององค์ประกอบที่สามารถนำออกได้ ลำดับขององค์ประกอบในอาร์เรย์สามารถเปลี่ยนได้ตามต้องการ

ตัวอย่าง

อินพุต - array = {12, 3, 11, 7, 5}

เอาต์พุต - 2

คำอธิบาย -

ก่อนอื่น เราจะเรียงอาร์เรย์จากน้อยไปมาก -

อาร์เรย์จะกลายเป็น {3, 5, 7, 11, 12}

จากนั้นนำออกทีละตัว

นำออก 3 - เวลารอคือ 0 ซึ่งน้อยกว่าเวลานำออก (3) สามารถนำออกได้

นำออก 5 - เวลารอคือ 3 ซึ่งน้อยกว่าเวลานำออก (5) สามารถนำออกได้

นำออก 7 - เวลารอคือ 8 ซึ่งมากกว่าเวลานำออก (7) ไม่สามารถนำออกได้

อัลกอริทึม

ขั้นตอนที่ 1: เรียงอาร์เรย์จากน้อยไปมาก
ขั้นตอนที่ 2: สำหรับแต่ละองค์ประกอบในอาร์เรย์ ทำ:
ขั้นตอนที่ 3: หาเวลารอ (ผลรวมเวลานำออกขององค์ประกอบก่อนหน้าทั้งหมด)
ขั้นตอนที่ 4: ถ้า (เวลารอ <= เวลานำออก)
    ขั้นตอน 4.1: นำออกและเพิ่มจำนวนนับ
ขั้นตอนที่ 5: มิฉะนั้น: หยุด
ขั้นตอนที่ 6: พิมพ์จำนวนองค์ประกอบที่นำออกได้

ตัวอย่างโปรแกรม

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

int countRemovedElements(int arr[], int n) {
    sort(arr, arr + n);
    int removeCount = 0;
    int waitTime = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] >= waitTime) {
            removeCount++;
            waitTime += arr[i];
        } else
            break;
    }
    return removeCount;
}

int main() {
    int arr[] = { 12, 3, 11, 7, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum number of elements that can be removed from the array is " << countRemovedElements(arr, n);
    return 0;
}

ผลลัพธ์

The maximum number of elements that can be removed from the array is 2

คำอธิบาย

กลยุทธ์ที่ดีที่สุดคือเรียงจากน้อยไปมาก (Greedy) เพื่อให้เวลารอสะสมน้อยที่สุด ทำให้นำออกได้มากที่สุด