Giá trị K tối đa sao cho mảng có ít nhất K phần tử >= K trong C++

Cho mảng arr. Tìm giá trị K lớn nhất sao cho mảng có ít nhất K phần tử lớn hơn hoặc bằng K.

Ví dụ

Đầu vào: arr[] = {3, 5, 1, 7, 6, 6, 4, 8}

Đầu ra: 5

Giải thích

Các phần tử >= 5: 5, 6, 6, 7, 8 (5 phần tử).

Phương pháp giải

Sắp xếp mảng, kiểm tra từ cuối về đầu xem số phần tử sau vị trí i có lớn hơn giá trị tại i không. Nếu có, trả về giá trị đó.

Ví dụ

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

int CalcMaximumVal(int arr[], int N) {
    sort(arr, arr + N);
    for (int i = N - 1; i >= 0; i--) {
        if (arr[i] <= (N - i))
            return arr[i];
    }
}

int main() {
    int arr[] = {4, 7, 2, 3, 8};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "Giá trị K tối đa sao cho mảng có ít nhất K phần tử >= K là " << CalcMaximumVal(arr, N);
    return 0;
}

Đầu ra

Giá trị K tối đa sao cho mảng có ít nhất K phần tử >= K là 3