สมมติว่าเรามีอาร์เรย์ที่มีองค์ประกอบ N เราต้องลบองค์ประกอบออกจากอาร์เรย์โดยทำตามการดำเนินการที่กำหนด การดำเนินการเป็นเหมือน เราต้องเลือกตัวเลขสองตัวใด ๆ ของอาร์เรย์ และลบขนาดใหญ่กว่า ค่าใช้จ่ายที่รวมอยู่ในการดำเนินการนี้จะเท่ากับจำนวนที่น้อยกว่า เราต้องลบองค์ประกอบเพียงครั้งละหนึ่งรายการ ตามการดำเนินการนี้ และดำเนินงานด้วยต้นทุนขั้นต่ำ สมมติว่าอาร์เรย์มี {4, 2, 5} ฉันเอา 4 กับ 2 ลบ 4 โดยจ่ายราคา 2 จากนั้นเราลบ 5 อีกครั้งด้วยราคา 2
วิธีการนั้นง่ายเกินไป อย่างที่เราทราบกันดีอยู่แล้วว่าต้นทุนจะเท่ากันกับอันที่เล็กกว่า ดังนั้นเพื่อลดต้นทุน เราจะเอาอันที่เล็กที่สุดและองค์ประกอบอื่นๆ บางส่วนออก แล้วเอาอันที่ใหญ่กว่าออก ต้นทุนก็จะเล็กลงทุกที ดังนั้นค่าใช้จ่ายทั้งหมดจะเป็น (N – 1)*จำนวนที่น้อยที่สุด
ตัวอย่าง
#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);
} ผลลัพธ์
Minimum cost: 4
