n개의 요소로 구성된 배열이 있다고 가정합니다. 모든 요소가 동일하도록 모든 요소의 가능한 최대 합을 찾으십시오. 허용되는 유일한 작업은 두 요소를 선택하고 둘 중 더 큰 요소를 두 요소의 절대 차이로 바꾸는 것입니다. 요소가 [9, 12, 3, 6]과 같다고 가정합니다. 그러면 출력은 12가 됩니다. 따라서 먼저 A[1]을 A[1] – A[3] =12 – 6 =6으로 바꿉니다. 이제 요소는 [9, 6, 3, 6]이고 A[ 3] A[3] – A[2] =6 – 3 =3입니다. 따라서 요소는 [9, 6, 3, 3]입니다. 그런 다음 A[0]을 A[0] – A[1] =9 – 6 =3으로 바꿉니다. 따라서 요소는 [3, 6, 3, 3]입니다. 그리고 마지막으로 A[1]을 A[1] – A[3] =6 – 3 =3으로 바꿉니다. 따라서 요소는 [3, 3, 3, 3]입니다. 따라서 모두 동일합니다. 합은 12입니다.
연산을 분석하면 A[i] =A[i] – A[j]가 됩니다. 여기서 A[i]> A[j]입니다. 따라서 우리는 두 개의 숫자를 취한 다음 더 큰 값을 절대 차이로 바꿉니다. 그런 다음 모두 같을 때까지 이 단계를 반복합니다.
예시
#include<iostream>
#include<algorithm>
using namespace std;
int findSameElement(int arr[], int n) {
int gcd_val = arr[0];
for (int i = 1; i < n; i++)
gcd_val = __gcd(arr[i], gcd_val);
return gcd_val;
}
int getMaxSum(int arr[], int n) {
int value = findSameElement(arr, n);
return (value * n);
}
int main() {
int arr[] = {3, 9, 6, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum sum is: " << getMaxSum(arr, n);
} 출력
The maximum sum is: 12