สมมติว่าเรามีโครงสร้างข้อมูลที่กำหนดไว้สำหรับข้อมูลประเภทจำนวนเต็ม ในการป้อนข้อมูลมาตรฐานของเรา เรามี n แบบสอบถาม ในแต่ละแบบสอบถาม (ในแต่ละบรรทัด) เรามีสององค์ประกอบ อันแรกเป็นตัวดำเนินการ อันที่สองคือองค์ประกอบ การดำเนินการจะเป็นดังนี้ -
-
แทรก. ซึ่งจะแทรกองค์ประกอบเข้าไปในชุด
-
ลบ. การดำเนินการนี้จะลบองค์ประกอบออกจากชุด (ถ้ามี)
-
ค้นหา. สิ่งนี้จะค้นหาองค์ประกอบในชุดหากแสดงใช่หรือไม่ใช่
ดังนั้น หากอินพุตเป็น n =7, คำสั่ง =[[1,5],[1,8],[1,3],[2,8],[1,9],[3,8], [3,3]] จากนั้นผลลัพธ์จะเป็น [No, Yes] เนื่องจากไม่มี 8 ในชุดและมี 3 อยู่
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดหนึ่งชุด s
- กำหนดหนึ่งชุด iterator 'it' เพื่อวนซ้ำผ่าน s
- q :=จำนวนคำค้นหา
- ในขณะที่ q ไม่ใช่ศูนย์ ให้ลด q หลังจากการวนซ้ำแต่ละครั้ง ให้ทำ:
- ใช้แบบสอบถามประเภท qt
- สำหรับ qt
- ถ้า qt เป็น 1 ให้ใส่ x s
- ออกมาจากบล๊อก
- ถ้า qt เป็น 2 ให้ลบ x ออกจาก s
- ออกมาจากบล๊อก
- ถ้า qt เป็น 3,
- เรียก find(x) ข้างในนั้น
- ถ้ามันเหมือนกับองค์ประกอบสุดท้ายของ s แล้ว:
- พิมพ์ไม่
- มิฉะนั้น
- พิมพ์ใช่
- ออกมาจากบล๊อก
- ถ้า qt เป็น 1 ให้ใส่ x s
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <iostream>
#include <set>
using namespace std;
int main(){
set<int> s;
set<int>::iterator it;
int q,x;
int qt;
cin >> q;
while(q--){
cin>>qt>>x;
switch(qt){
case 1:s.insert(x);
break;
case 2:s.erase(x);
break;
case 3:it=s.find(x);
if(it==s.end())
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
break;
}
}
return 0;
}
อินพุต
7 1 5 1 8 1 3 2 8 1 9 3 8 3 3
ผลลัพธ์
No Yes
