타워에 대해 달성할 수 있는 최소한의 추함을 찾는 C++ 프로그램

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. n개의 블록 타워가 연속적으로 있다고 가정합니다. i번째 타워의 높이는 A[i]입니다. 하루에 작업을 수행할 수 있습니다. 두 개의 인덱스 i와 j(i !=j)를 선택하고 타워 i에서 j로 다시 이동합니다. A[i]는 1 감소하고 A[j]는 1 증가합니다. 건물의 추함은 max(A) - min(A)입니다. 우리가 달성할 수 있는 최소한의 추함을 찾아야 합니다.

따라서 입력이 A =[1, 2, 3, 1, 5]와 같으면 출력은 1이 됩니다. i=2 및 j=0에 대해 세 가지 작업을 수행할 수 있기 때문에 새 배열은 이제 [ 2,2,2,1,5], i =4 및 j =3인 경우 배열은 [2,2,2,2,4]이고 i =4 및 j =2인 경우 배열은 [ 2,2,3,2,3].

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
}

입력

{ 1, 2, 3, 1, 5 }