ข้อความโจทย์
กำหนดเซตของ n จำนวนเต็ม ให้ดำเนินการน้อยที่สุด (สามารถแทรก/ลบสมาชิกเข้า/ออกจากเซต) เพื่อทำให้ MEX ของเซตเท่ากับ x (ที่กำหนดให้)
หมายเหตุ − MEX ของเซตจำนวนเต็มคือจำนวนเต็มบวกหรือศูนย์ที่น้อยที่สุดที่ไม่มีอยู่ในเซต เช่น MEX ของ {0, 2, 4} คือ 1 และ MEX ของ {1, 2, 3} คือ 0
ตัวอย่าง
ถ้า n = 5 และ x = 3 และอาร์เรย์คือ {0, 4, 5, 6, 7} ต้องการการดำเนินการขั้นต่ำ 2 ครั้ง
อัลกอริทึม
- แนวทางคือในเซตสุดท้าย สมาชิกทั้งหมดที่น้อยกว่า x ควรมีอยู่, x ไม่ควรอยู่ และสมาชิกที่มากกว่า x ไม่สำคัญ
- นับจำนวนสมาชิกที่น้อยกว่า x ที่ไม่มีอยู่ในเซตเริ่มต้น และบวกเข้าไปในคำตอบ
- ถ้า x มีอยู่ ให้บวก 1 เข้าไปในคำตอบ เพราะ x ควรถูกลบออก
ตัวอย่าง
#include <iostream> using namespace std; int getMinOperations(int *arr, int n, int x) { int k = x, i = 0; while (n--) { if (arr[n] < x) { --k; } if (arr[n] == x) { ++k; } } return k; } int main() { int arr[] = {0, 4, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); int x = 3; cout << "Minimum required operations = " << getMinOperations(arr, n, x) << endl; return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้
Minimum required operations = 2
