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

ในปัญหานี้ เราจะได้รับอาร์เรย์ขององค์ประกอบ N งานของเราคือค้นหาการลบสูงสุดจากอาร์เรย์เมื่อเวลาลบ>=เวลารอ

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

องค์ประกอบมีเวลารอซึ่งเป็นเวลาที่จะต้องรอจนกว่าจะถูกลบออก

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

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

ลองมาดูตัวอย่างเพื่อทำความเข้าใจปัญหา

ป้อนข้อมูล − อาร์เรย์ ={12, 3, 11, 7, 5}

ผลผลิต − 2

คำอธิบาย −

อันดับแรก เราจะเรียงลำดับอาร์เรย์ใหม่เป็นลำดับจากน้อยไปมาก -

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

ตอนนี้เราจะลบองค์ประกอบทีละรายการ

กำลังลบ 3 − เวลารอคือ 0 ซึ่งน้อยกว่าเวลานำออก (3) การกำจัดเป็นไปได้

กำลังลบ 5 − เวลารอคือ 3 ซึ่งน้อยกว่าเวลานำออก (5) การกำจัดเป็นไปได้

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

เพื่อแก้ปัญหานี้ เราจะทำการจัดเรียงและตรวจสอบองค์ประกอบที่จะลบออกทีละรายการ

อัลกอริทึม

Step 1: Sort the array in ascending order.
Step 2: For every element in the array, Do:
Step 3: Find waiting Time (sum of removal time of all elements before the element).
Step 4: if (waiting time <= removal time )
   step 4.1: remove the element and increase the remove count.
Step 5: else: break.
Step 6: print the number of elements removed.

ตัวอย่าง

โปรแกรมค้นหาการลบสูงสุดจากอาร์เรย์เมื่อถึงเวลาลบ>=เวลารอใน C++

#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