Số phần tử loại bỏ tối đa khi thời gian loại bỏ ≥ thời gian chờ C++

Cho mảng N phần tử, mỗi phần tử biểu diễn thời gian loại bỏ (removal time). Phần tử có thời gian chờ (waiting time) bằng tổng thời gian loại bỏ của các phần tử trước nó. Chỉ loại bỏ được nếu removal time ≥ waiting time. Tìm số phần tử loại bỏ được tối đa (có thể sắp xếp lại mảng).

Ví dụ

Input: {12, 3, 11, 7, 5} → Output: 2

Giải thích: Sắp xếp tăng: {3, 5, 7, 11, 12}. Loại bỏ 3 (wait=0 ≤ 3), loại bỏ 5 (wait=3 ≤ 5), loại bỏ 7 (wait=8 > 7) → dừng. Kết quả: 2.

Thuật toán

1. Sắp xếp mảng tăng dần.
2. Duyệt từng phần tử, tính waiting time (tổng các phần tử đã loại).
3. Nếu arr[i] ≥ waitTime → loại bỏ, tăng count, cập nhật waitTime.
4. Ngược lại → dừng.

Ví dụ minh họa

#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;
}

Kết quả

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

Độ phức tạp: O(n log n) do sắp xếp. Chiến lược tham lam: ưu tiên loại bỏ phần tử nhỏ trước để giảm waiting time.