Đề bài
Cho một mảng "arr" kích thước n và phần tử x, nhiệm vụ là tìm số lượng phần tử tối thiểu cần thêm vào mảng để trung vị bằng x.
Trung vị trong mảng độ dài n là phần tử chiếm vị trí số (n-1)/2 sau khi sắp xếp các phần tử theo thứ tự không giảm. Ví dụ, trong mảng dưới đây trung vị là 20:
arr1[] = {10, 20, 30, 40}
Nếu arr[] = {1, 2, 3} và x = 4 thì phải thêm 4 số tức là {4, 5, 5, 5} vào mảng để trung vị bằng 4.
Thuật toán
Thuật toán rất đơn giản. Chúng ta phải thêm số x vào mảng cho đến khi trung vị của mảng bằng x.
Ví dụ
#include <iostream> #include <algorithm> using namespace std; int minNumbersToBeAdded(int *arr, int n, int x){ sort(arr, arr + n); int cnt = 0; while (arr[(n - 1)/2] != x) { arr[n] = x; ++n; sort(arr, arr + n); ++cnt; } return cnt; } int main(){ int arr[20] = {1, 2, 3}; int x = 4; int n = 3; cout << "Minimum numbers to be added = " << minNumbersToBeAdded(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:
Minimum numbers to be added = 4