Giả sử chúng ta có một mảng A với 3 phần tử. A[1] là trung bình cộng của hai phần tử A[0] và A[2] nếu A[0] + A[2] = 2 * A[1]. Độ lệch trung bình cộng của ba số d(A[0], A[1], A[2]) là |A[0] + A[2] - 2*A[1]|. Chúng ta có thể thực hiện các phép toán sau bất kỳ số lần nào: Chọn hai chỉ số i và j từ tập {0, 1, 2} sao cho i != j, sau đó tăng A[i] lên 1 và giảm A[j] đi 1. Chúng ta phải tìm giá trị nhỏ nhất của độ lệch trung bình cộng.
Ví dụ, nếu đầu vào là A = [2, 2, 6], thì đầu ra sẽ là 1, vì nếu giảm A[0] và tăng A[1], mảng sẽ trở thành [1, 3, 6], lúc này độ lệch trung bình cộng sẽ là |1 + 6 - 2 * 3| = 1.
Các bước thực hiện
Để giải quyết bài toán này, chúng ta thực hiện theo các bước sau:
a := A[0] b := A[1] c := A[2] return minimum của 1 và (((a + c - 2 * b) mod 3 + 3) mod 3)
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A) { int a = A[0]; int b = A[1]; int c = A[2]; return min(1, ((a + c - 2 * b) % 3 + 3) % 3); } int main() { vector<int> A = { 2, 2, 6 }; cout << solve(A) << endl; }Đầu vào
{ 2, 2, 6 }Đầu ra
1