ในปัญหานี้ เราได้รับอาร์เรย์ arr ขนาด n งานของเราคือ ค้นหาจำนวนการดำเนินการที่จำเป็นในการทำให้องค์ประกอบอาร์เรย์ทั้งหมดเท่ากัน
การดำเนินการถูกกำหนดเป็น การกระจายน้ำหนักเท่ากันจากองค์ประกอบที่มีน้ำหนักสูงสุดไปยังองค์ประกอบทั้งหมดของอาร์เรย์ .
หากไม่สามารถทำให้องค์ประกอบอาร์เรย์เท่ากันได้ ให้พิมพ์ -1
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : arr[] = {7, 3, 3, 3}
Output : 3 คำอธิบาย
อาร์เรย์หลังการแจกจ่ายคือ $4, 4, 4, 4}
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการหาค่าที่ใหญ่ที่สุดของอาร์เรย์ จากนั้นใช้ค่าที่ใหญ่ที่สุดนี้ตรวจสอบว่าองค์ประกอบทั้งหมดของอาร์เรย์มีค่าเท่ากันหรือไม่ และค่าเท่ากับการลบ n (หรือทวีคูณ) จากค่าสูงสุดของอาร์เรย์ ถ้าใช่ ให้คืนค่า n ถ้าไม่ใช่ ให้คืนค่า -1 (แสดงว่าเป็นไปไม่ได้)
ตัวอย่าง
มาดูตัวอย่างทำความเข้าใจปัญหากัน
#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;
} ผลลัพธ์
The number of operations required to make all array elements Equal is 3
