Chương trình C ++ để tìm mức độ xấu tối thiểu mà chúng ta có thể đạt được của tháp

Giả sử chúng ta có một mảng A với n phần tử. Coi có n khối tháp liên tiếp. Tháp thứ i có chiều cao A [i]. Trong một ngày, chúng ta có thể thực hiện thao tác:Chọn hai chỉ số i và j (i! =J) và chuyển ngược lại từ tháp i sang tháp j. Nó sẽ giảm A [i] đi 1 và tăng A [j] lên 1. Độ xấu của các tòa nhà là max (A) - min (A). Chúng ta phải tìm ra mức độ xấu nhất có thể có mà chúng ta có thể đạt được.

Vì vậy, nếu đầu vào là A =[1, 2, 3, 1, 5], thì đầu ra sẽ là 1, bởi vì chúng ta có thể thực hiện ba phép toán cho i =2 và j =0, mảng mới bây giờ sẽ là [ 2,2,2,1,5], thì với i =4 và j =3, mảng sẽ là [2,2,2,2,4], và với i =4 và j =2, mảng là [ 2,2,3,2,3].

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

sum := 0
x := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   sum := sum + A[i]
if sum mod n is same as 0, then:
   return 0
return 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   int sum = 0, x = 0;
   int n = A.size();
   for (int i = 0; i < n; i++)
      sum += A[i];
   if (sum % n == 0)
      return 0;
   return 1;
}
int main() {
   vector<int> A = { 1, 2, 3, 1, 5 };
   cout << solve(A) << endl;
}

Đầu vào

{ 1, 2, 3, 1, 5 }

Đầu ra

1