คำชี้แจงปัญหา
กำหนดชุดของจำนวนเต็ม 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
