ข้อความปัญหา
ได้รับอาร์เรย์ของจำนวนเต็มที่ไม่เป็นลบ หา 3 องค์ประกอบจากอาร์เรย์ที่สร้างสามเหลี่ยมได้และมีเส้นรอบรูปสูงสุด
ตัวอย่าง
ถ้าอาร์เรย์อินพุตคือ {5, 1, 3, 5, 7, 4} เส้นรอบรูปสูงสุดคือ (7 + 5 + 5) = 17
อัลกอริทึม
- เรียงอาร์เรย์จากมากไปน้อย (Non-increasing) ดังนั้นตัวแรกจะมากที่สุด และตัวสุดท้ายน้อยที่สุด
- ถ้า 3 ตัวแรกของอาร์เรย์ที่เรียงแล้วสร้างสามเหลี่ยมได้ จะเป็นสามเหลี่ยมเส้นรอบรูปสูงสุด
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int getMaxPerimeter(int *arr, int n) {
sort(arr, arr + n, greater<int>());
int maxPerimeter = 0;
for (int i = 0; i < n - 2; ++i) {
if (arr[i] < arr[i + 1] + arr[i + 2]) {
maxPerimeter = max(maxPerimeter, arr[i] + arr[i+1] + arr[i+2]);
break;
}
}
if (maxPerimeter) {
return maxPerimeter;
}
return -1;
}
int main() {
int arr[] = {5, 1, 3, 5, 7, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int maxPerimeter;
maxPerimeter = getMaxPerimeter(arr, n);
if (maxPerimeter != -1) {
cout << "Max perimeter = " << maxPerimeter << endl;
} else {
cout << "Triangle formation is not possible" << endl;
}
return 0;
}
ผลลัพธ์
Max perimeter = 17
คำอธิบาย
เงื่อนไขสามเหลี่ยม: ผลรวมของด้านสองด้านต้องมากกว่าด้านที่สาม สำหรับอาร์เรย์ที่เรียงจากมากไปน้อย หาก a ≥ b ≥ c แล้ว a < b + c ก็เพียงพอ (เพราะ b + c > a หมายความว่า b + a > c และ c + a > b เป็นจริงอัตโนมัติ)
การ break หลังเจอชุดแรกที่ทำให้เป็นสามเหลี่ยมได้ เนื่องจากชุดแรกจะมีเส้นรอบรูปมากที่สุดแล้ว (เพราะเรียงจากมากไปน้อย)
