หาตำแหน่งบุคคลที่สามบน N-เหลี่ยมสมมาตรใน C++

บทนำ

โจทย์: บน N-เหลี่ยมสมมาตร มีคนอยู่ 2 คน ที่มุม A และ B หามุมที่ 3 ที่ทำให้ผลรวมระยะทางไปยัง A และ B น้อยที่สุด

ขั้นตอนการแก้ปัญหา

1. วนลูปทุกมุม i = 1 ถึง N (ข้าม A และ B)
2. คำนวณ |i - A| + |i - B| (ระยะทางแบบ Manhattan บนมุม)
3. เลือกมุมที่ให้ผลรวมน้อยที่สุด

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int findThirdPersonStandingVertex(int N, int A, int B) {
    int position = 0;
    int minimum_sum = INT_MAX, sum;
    for (int i = 1; i <= N; i++) {
        if (i == A || i == B) {
            continue;
        } else {
            sum = abs(i - A) + abs(i - B);
            if (sum < minimum_sum) {
                minimum_sum = sum;
                position = i;
            }
        }
    }
    return position;
}

int main() {
    int N = 7, A = 5, B = 7;
    cout << "Vertex: " << findThirdPersonStandingVertex(N, A, B) << endl;
    return 0;
}

ผลลัพธ์

Vertex: 6

คำอธิบาย

N=7, A=5, B=7 มุมที่เป็นไปได้: 1,2,3,4,6 ระยะทาง: 1→|4|+|6|=10, 2→|3|+|5|=8, 3→|2|+|4|=6, 4→|1|+|3|=4, 6→|1|+|1|=2 ← น้อยที่สุด

สรุป

โจทย์หาจุดที่ Minimize Sum of Distances บนกราฟวงจร (Cycle Graph) แบบ Brute Force O(N) เพียงพอสำหรับ N ปานกลาง