Đề bài
Cho một mảng số nguyên arr, nhiệm vụ là in ra số phép toán tối thiểu cần thiết để xóa tất cả các phần tử của mảng. Khi xóa phần tử, hạn chế sau được áp dụng:
- Bất kỳ phần tử nào từ mảng có thể được chọn ngẫu nhiên và mọi phần tử chia hết cho nó có thể bị loại khỏi mảng.
Nếu arr[] = {2, 4, 15, 10, 8, 5, 3} thì cần 3 phép toán để xóa tất cả các phần tử:
- Nếu chọn 2 thì sẽ xóa {2, 4, 10, 8}
- Nếu chọn 5 thì sẽ xóa {5, 15}
- Nếu chọn 3 thì sẽ xóa {3}
Thuật toán
1. Sắp xếp mảng theo thứ tự tăng dần và đếm số lần xuất hiện của mỗi phần tử 2. Với mỗi phần tử chưa được đánh dấu bắt đầu từ đầu, đánh dấu tất cả các phần tử chia hết cho phần tử được chọn, và tăng bộ đếm kết quả
Ví dụ
#include <iostream> #include <algorithm> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) #define MAX 100 using namespace std; int getMinOperations(int *arr, int n){ int map[MAX] = {0}; sort(arr, arr + n); for (int i = 0; i < n; ++i) { map[arr[i]]++; } int cnt = 0; for (int i = 0; i < n; ++i) { if (map[arr[i]]) { for (int j = i; j < n; ++j) { if (arr[j] % arr[i] == 0) { map[arr[j]] = 0; } } ++cnt; } } return cnt; } int main(){ int arr[] = {2, 4, 15, 10, 8, 5, 3}; cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << 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 required operations = 3