คำชี้แจงปัญหา
จากอาร์เรย์ของจำนวนเต็มบวก N ภารกิจคือการหาจำนวนเต็มบวกที่เล็กที่สุดที่สามารถวางไว้ระหว่างสององค์ประกอบใด ๆ ของอาร์เรย์นั้นได้ว่าผลรวมขององค์ประกอบในอาร์เรย์ย่อยที่เกิดขึ้นก่อนหน้านั้นเท่ากับผลรวมขององค์ประกอบที่เกิดขึ้น ในอาร์เรย์ย่อยหลังจากนั้น โดยมีจำนวนเต็มที่วางใหม่รวมอยู่ในอาร์เรย์ย่อยทั้งสอง
ตัวอย่าง
ถ้า arr ={3, 2, 1, 5, 7, 10} แล้ว output จะเป็น 6 ถ้าเราใส่ค่า 6 ไว้ระหว่าง 5 ถึง 7 ผลรวมของ subarray ด้านซ้ายและขวาจะเท่ากันดังนี้ −
+ 2 + 1 + 5 + 6 =17
7 + 10 =17
อัลกอริทึม
- ให้ผลรวมของอาร์เรย์ทั้งหมดเป็น S
- แนวคิดคือการหาผลรวมด้านซ้ายจนถึงดัชนี i (รวมไว้ด้วย) ให้ผลรวมนี้เป็น L
- ตอนนี้ผลรวมของ subarray arri+1 .. N คือ 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
