Trong bài toán này, chúng ta được cho một mảng arr kích thước n. Nhiệm vụ của chúng ta là Tìm số phép toán cần thiết để làm tất cả phần tử mảng bằng nhau
Phép toán được định nghĩa là phân phối trọng lượng bằng nhau từ phần tử có trọng lượng lớn nhất đến tất cả phần tử của mảng.
Nếu không thể làm các phần tử mảng bằng nhau, in -1.
Hãy xem ví dụ sau để hiểu bài toán,
Input : arr[] = {7, 3, 3, 3} Output : 3Giải thích
Mảng sau phân phối là {4, 4, 4, 4}
Phương pháp giải
Một giải pháp đơn giản là tìm giá trị lớn nhất của mảng. Sau đó dùng giá trị lớn nhất này kiểm tra xem tất cả phần tử có bằng nhau và giá trị bằng phép trừ n (hoặc bội số) từ giá trị lớn nhất. Nếu có, trả về n, nếu không, trả về -1 (ý chỉ không thể).
Ví dụ
Hãy xem ví dụ để hiểu bài toán
#include<bits/stdc++.h> using namespace std; int findOperationCount(int arr[],int n){ int j = 0, operations = 0; int maxVal = arr[0]; int minVal = arr[0]; int maxValInd = 0; for (int i = 1; i < n; i++){ if(arr[i] > maxVal){ maxVal = arr[i]; maxValInd = i; } if(arr[i] < minVal){ minVal = arr[i]; } } for (int i =0;i<n;i++){ if (arr[i] != maxVal && arr[i] <= minVal && arr[i] != 0){ arr[j] += 1; arr[maxValInd] -= 1; maxVal -= 1; operations += 1; j += 1; } else if (arr[i] != 0){ j += 1; } } for (int i = 0; i < n; i++){ if (arr[i] != maxVal){ operations = -1; break; } } return operations; } int main(){ int arr[] = {4, 4, 8, 4}; int n = sizeof(arr)/sizeof(arr[0]); cout<<"The number of operations required to make all array elements Equal is "<<findOperationCount(arr, n); return 0; }Kết quả
The number of operations required to make all array elements Equal is 3