ลดต้นทุนให้น้อยที่สุดด้วยการลบสมาชิกและเลือกต้นทุนจากค่าน้อยกว่า ใน C++

บทนำ

กำหนดอาร์เรย์ N สมาชิก ต้องการลบสมาชิกออกจากอาร์เรย์โดยปฏิบัติตามกฎ: เลือกสองจำนวนใดๆ ลบตัวที่มากกว่า ต้นทุนเท่ากับตัวที่น้อยกว่า ลบทีละหนึ่งจนหมด ต้องการต้นทุนรวมน้อยที่สุด

ตัวอย่าง: อาร์เรย์ {4, 2, 5} → เลือก 4,2 ลบ 4 ต้นทุน 2 → เหลือ {2,5} → เลือก 2,5 ลบ 5 ต้นทุน 2 → รวมต้นทุน 4

แนวคิด

เนื่องจากต้นทุนเสมอเท่ากับตัวเลขที่น้อยกว่า กลยุทธ์ที่ดีที่สุดคือใช้สมาชิกที่มีค่าน้อยที่สุดจับคู่กับสมาชิกอื่นๆ ทีละตัว ต้นทุนรวม = (N - 1) × ค่าน้อยที่สุด

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

#include <iostream>
#include <algorithm>
using namespace std;

int getMinimumCost(int arr[], int n) {
    int smallest = *min_element(arr, arr + n);
    return smallest * (n - 1);
}

int main() {
    int arr[] = {4, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum cost: " << getMinimumCost(arr, n);
    return 0;
}

ผลลัพธ์

Minimum cost: 4