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