Giả sử chúng ta có một mảng A với n phần tử. Xét có n tháp khối xếp thành một hàng. Tháp thứ i có chiều cao A[i]. Trong một ngày, chúng ta có thể thực hiện phép toán: Chọn hai chỉ số i và j (i != j) và di chuyển khối từ tháp i sang 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 độ xấu tối thiểu có thể đạt được.
Ví dụ, nếu đầu vào là A = [1, 2, 3, 1, 5], thì đầu ra sẽ là 1, vì ta có thể làm ba phép toán cho i=2 và j=0, mảng mới sẽ là [2,2,2,1,5], sau đó cho i = 4 và j = 3, mảng sẽ là [2,2,2,2,4], và cho i = 4 và j = 2, mảng là [2,2,3,2,3].
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
sum := 0 x := 0 n := kích thước của A for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: sum := sum + A[i] if sum mod n bằng 0, thì: return 0 return 1
Ví dụ
Xem 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