Đề bài
Cho một tập hợp n số nguyên, thực hiện số phép toán tối thiểu (có thể chèn/xóa phần tử vào/từ tập hợp) để làm cho MEX của tập hợp bằng x (đã cho).
Lưu ý − MEX của một tập hợp số nguyên là số nguyên không âm nhỏ nhất không tồn tại trong nó. Ví dụ, MEX của tập {0, 2, 4} là 1 và MEX của tập {1, 2, 3} là 0.
Ví dụ
Nếu n = 5 và x = 3 và mảng là {0, 4, 5, 6, 7} thì cần tối thiểu 2 phép toán.
Thuật toán
- Cách tiếp cận là thấy rằng trong tập hợp cuối cùng, tất cả các phần tử nhỏ hơn x phải tồn tại, x không được tồn tại và bất kỳ phần tử lớn hơn x không quan trọng.
- Vì vậy, chúng ta sẽ đếm số phần tử nhỏ hơn x không tồn tại trong tập ban đầu và cộng vào đáp án.
- Nếu x tồn tại, chúng ta sẽ cộng 1 vào đáp án vì x phải bị xóa.
Ví dụ
#include <iostream>
using namespace std;
int getMinOperations(int *arr, int n, int x) {
int k = x, i = 0;
while (n--) {
if (arr[n] < x) {
--k;
}
if (arr[n] == x) {
++k;
}
}
return k;
}
int main() {
int arr[] = {0, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 3;
cout << "Số phép toán tối thiểu = " << getMinOperations(arr, n, x) << endl;
return 0;
}
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Số phép toán tối thiểu = 2