Holiday of Equality

Holiday of Equality

Codeforces easy

لدينا مصفوفة \(A\) تحتوي على \(N\) من الأعداد الصحيحة. يمكنك زيادة أي عنصر بمقدار \(1\) أي عدد من المرات. أوجد الحد الأدنى لإجمالي عدد الزيادات المطلوبة لجعل جميع العناصر متساوية.

Solution

لجعل جميع العناصر متساوية بأقل عدد ممكن من الزيادات، نحتاج إلى رفع كل العناصر إلى القيمة العظمى في المصفوفة. ولفعل ذلك، سنكتب دالة تحسب القيمة العظمى بين قيمتين.

int max_function(int x, int y) {
    if (x > y) return x;
    else return y;
}

بعد ذلك، سنحسب القيمة العظمى في المصفوفة \(max(A_1, \dots, A_n)\) بالطريقة التالية.

int n;
cin >> n;

int a[n];
for (int i = 0; i < n; i++) {
    cin >> a[i];
}

int max_value = a[0];
for (int i = 0; i < n; i++) {
    max_value = max_function(max_value, a[i]);
}

لكل عنصر \(i\)، كمية الزيادة المطلوبة هي \(max(A_1, \dots, A_n) - A_i\).
بجمع هذه القيم لجميع العناصر نحصل على الحد الأدنى لإجمالي عدد الزيادات المطلوبة.

int coins = 0;
for (int i = 0; i < n; i++) {
    coins += max_value - a[i];
}

cout << coins;