문제 설명
N개의 양의 정수 배열이 주어졌을 때, 그 작업은 배열의 임의의 두 요소 사이에 위치할 수 있는 가장 작은 양의 정수를 찾는 것입니다. 두 개의 하위 배열 중 하나에 새로 배치된 정수가 포함된 뒤의 하위 배열
예시
arr ={3, 2, 1, 5, 7, 10}이면 출력은 6입니다. 값 6을 5와 7 사이에 배치하면 왼쪽 및 오른쪽 하위 배열의 합은 다음과 같이 됩니다. -
+ 2 + 1 + 5 + 6 =17
7 + 10 =17
알고리즘
- 전체 배열의 합을 S로 둡니다.
- 아이디어는 인덱스 i(포함)까지 왼쪽 합계를 찾는 것입니다. 이 합계를 L로 둡니다.
- 이제 부분배열 arri+1 ..의 합은 S – L입니다. 이 합을 R이라고 합니다.
- 두 하위 배열의 합은 같다고 가정하므로 위에서 얻은 두 합 L과 R 중 큰 값을 이 두 가지 중 작은 합과 큰 합과 큰 합 사이의 차이 값으로 줄여야 합니다. 더 작은 합계는 필요한 양의 정수 값입니다.
예시
#include <iostream>
#include <numeric>
#include <climits>
using namespace std;
int getMinimumSplitPoint(int *arr, int n) {
int sum = 0;
sum = accumulate(arr, arr + n, sum);
int leftSum = 0;
int rightSum = 0;
int minValue = INT_MAX;
for (int i = 0; i < n - 1; ++i) {
leftSum += arr[i]; rightSum = sum - leftSum;
if (leftSum > rightSum) {
int e = leftSum - rightSum;
if (e < minValue) {
minValue = e;
}
} else {
int e = rightSum - leftSum;
if (e < minValue) {
minValue = e;
}
}
}
return minValue;
}
int main() {
int arr[] = {3, 2, 1, 5, 7, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int minValue = getMinimumSplitPoint(arr, n);
cout << "Element " << minValue << " needs to be inserted\n";
return 0;
} 출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Element 6 needs to be inserted