คำอธิบายปัญหา
ได้รับอาร์เรย์ arr[] ขนาด m ที่เก็บความยาวของช่วงเส้นตรง (Line Segments)
ช่วงเส้นตรงมีดังนี้: [0, arr[0]], [arr[0], arr[0]+arr[1]], [arr[0]+arr[1], arr[0]+arr[1]+arr[2]], ... ต้องการหา ลำดับช่วง (Segment Number) ที่จุดกึ่งกลาง (Midpoint) ของเส้นตรงทั้งหมดอยู่อยู่
ตัวอย่าง
Input: arr[] = {5, 7, 13}
Output: 3
คำอธิบาย: ช่วงเส้นตรงคือ: (0, 5), (5, 12), (12, 25) → ความยาวรวม = 25 → จุดกึ่งกลาง = 12.5 → อยู่ในช่วงที่ 3 (12 ถึง 25)
แนวทางแก้ปัญหา
- คำนวณ ผลรวมความยาวทั้งหมด (arrSum)
- หา จุดกึ่งกลาง (centerPoint) = arrSum / 2.0
- สะสมความยาวทีละช่วง (
sum):- ถ้า
sum == centerPoint→ จุดกึ่งกลางตรงปลายช่วง → คืนค่า -1 - ถ้า
sum > centerPoint → จุดกึ่งกลางอยู่ในช่วงนี้ → คืนค่า ลำดับช่วง (i+1)
- ถ้า
โค้ดตัวอย่าง C++
#include <iostream>
using namespace std;
int findSegmentWithMidPoint(int n, int m, int segment_length[]) {
double centerPoint = (1.0 * n) / 2.0;
int sum = 0;
int segment = 0;
for (int i = 0; i < m; i++) {
sum += segment_length[i];
if ((double)sum == centerPoint) {
segment = -1;
break;
}
if (sum > centerPoint) {
segment = i + 1;
break;
}
}
return segment;
}
int main() {
int m = 3;
int segment_length[] = { 5, 7, 13 };
int arrSum = 0;
for (int i = 0; i < m; i++)
arrSum += segment_length[i];
int ans = findSegmentWithMidPoint(arrSum, m, segment_length);
cout << "The segment number where middle point lies is " << ans;
return 0;
}
ผลลัพธ์
The segment number where middle point lies is 3
