Tuyên bố vấn đề
Cho một mảng gồm N số nguyên dương, nhiệm vụ là tìm số nguyên dương nhỏ nhất có thể được đặt giữa hai phần tử bất kỳ của mảng sao cho tổng các phần tử trong mảng con xuất hiện trước nó bằng tổng các phần tử xuất hiện. trong mảng con sau nó, với số nguyên mới đặt được bao gồm trong một trong hai mảng con
Ví dụ
Nếu arr ={3, 2, 1, 5, 7, 10} thì đầu ra là 6. Nếu chúng ta đặt giá trị 6 trong khoảng từ 5 đến 7 thì tổng của mảng con trái và phải sẽ bằng nhau như sau -
+ 2 + 1 + 5 + 6 =17
7 + 10 =17
Thuật toán
- Cho tổng của cả mảng bằng S
- Ý tưởng là tìm tổng bên trái cho đến chỉ số i (bao gồm cả nó). Gọi tổng này là L
- Bây giờ tổng của mảng con là + 1 .. N là S - L. Gọi tổng này là R
- Vì tổng của hai phân thức con được cho là bằng nhau, tổng lớn hơn của hai tổng L và R thu được ở trên, sẽ được giảm xuống giá trị của tổng nhỏ hơn giữa hai phân thức này và sự khác biệt giữa tổng lớn hơn và tổng nhỏ hơn, sẽ là giá trị của số nguyên dương bắt buộc.
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Element 6 needs to be inserted