Өмнө нь priority queue-н талаар болон queue, vector-г хэрхэн өөрсдөө бичих тухай ярьсан билээ. Одоо priority queue буюу min heap бүтцийн тухай дэлгэрэнгүй бичье. Эргэн санавал энэхүү өгөгдлийн бүтэц нь үндсэн 4 үйлдэлтэй ба: size() - heap-н хэмжээг буцаах front() - хамгийн бага элементийг буцаах pop() - хамгийн бага элементийг устгах push(element) - heap-д элемент нэмэх Үүнийг хэрхэн бичих вэ? Бид зүгээр л энгийн array ашиглаад хийж болох уу?...
Би queue-г хэрхэн бичих талаар энд бичсэн ба vector-н тухай мөн бичсэн. Энэ удаа өмнөх queue-г хэрхэн бичсэнтэй адилаар dynamic array-г хэрхэн хийж болох талаар бичихээр шийдлээ. Dynamic array-р нь энгийн array-с ялгаатай нь хэмжээгээ өөрчлөх боломжтойгоор онцлог ба үүний нэг нь vector билээ. Мэдээж vector-н ямарч элементийг мэдэхэд O(1) үйлдэл хийдэг ба vector-т үндсэн 3 үйлдэл байдаг гэвэл size() - хэмжээг мэдэх push(element) - шинэ элемент хамгийн хойно нэмэх [index] - index-р элементийн утгыг мэдэх Үүнийг яаж хийх хэр хэцүү байх талаар цааш уншихаас өмнө хэсэг бодоод үзээрэй....
Queue-н тухай өмнө нь бичсэн билээ. Энэ удаа үүнийг хэрхэн анхнаас нь бичих вэ? гэдэг талаар бичье. Үүний тулд заагч болон санах ойн тухай энгийн ойлголттой байхад хангалттай. Queue-д гол 4 үйлдэл байдаг ба size() - хэмжээг нь буцаадаг top() - эхний элемэнтийг буцаах pop() - эхний элемэнтийг устгах push(element) - хамгийн ард элемэнт нэмэх Мэдээж тийм ч хэцүү биш байлгүүдээ? Зүгээр array ашиглаад хийж болох уу? Болох бол яаж вэ?...
Санах ой болон заагч Бид бүхэн array, vector зэргийг хэрхэн үүсгэх ашиглаж болох талаар ярилцсан. Гэхдээ эдгээр зүйлс нь цаанаа хэрхэн дүрслэгддэг талаар ойлголт байхгүй байгаа билээ. Үүний тухай бичье. Мэдээж эдгээр бүх хувьсагч санах ойд хадгалагддаг. Жишээ нь бид array, vector үүсгэх үед c++ нь санах ойд үүсгэж бид шууд ашиглах боломжтой болдог. Хэрвээ бид эдгээр хувьсагчийг ашиглахгүй бол, эдгээр нь шууд цэвэрлэгдээд явдаг. Жишээ нь функц дотор зарласан хувьсагч шиг....
Анхны тоо Анхы тоо гэдэг нь яг 2 ширхэг ялгаатай хуваагчтай натурал тоог хэлдэг. Жишээ нь 2, 3, 5, 7 гэх мэт үргэлжлээд явна. N гэсэн тоо өгөгдөхөд тухайн тоог анхны тоо эсэхийг хэрхэн мэдэх вэ? Мэдээж бид [1, N] завсарт гүйгээд N тоог маань хэд нь хувааж байгаа вэ гэдгийг тоолоход болно. Үүнээс хурднаар шалгаж чадах уу? Анхны тоо зөвхөн 2 хуваагчтай гэхээр 1 болон өөртөө л хуваагддаг гэсэн үг ба N тоог [2, N-1] завсарт ямар ч тоо хуваадаггүй бол анхны тоо мөн....
Хоёртын хайлт гэх алгоритм хаа сайгүй л явж байдагдаа. Энгийн мөртлөө хүчтэй санааг агуулж байдаг. Ер нь нэрнүүдэд их учир бий шүү. Жишээ бодлого дээр авж үзье. Бодлого Бидэнд өсөхөөр эрэмбэлэгдсэн N урттай дараалал, Q ширхэг хүсэлт өгөгдөх ба хүсэлт бүрд нэг тоо байх ба энэ дараалалд тэр тоо байгаа эсэхэд хариулах юм. 1 <= N, Q <= 10^5, abs(a[i]) <= 10^9. Analysis Хүсэлт бүрийн хувьд N ширхэг тоо бүртэйгээ тэнцүү эсэхийг шалгахад болно....
Програмчлалыг хэрхэн сурах вэ? Миний хувьд хэрхэн бичдэг юу хийдгийг уншаад дараа нь бодлого бодож эхэлсэн. Тийм болхоор эхний ээлжинд C, C++ програмчлалын хэлний энгийн үйлдлүүд түүний тухай бичих гэж байна. Сая хэлсэнчлэн бодлого бодох нь маш хэрэгтэй ба анх эхэлж байгаа бол энэ сайтаас эхлээд бодоод явбал зүгээр. Англиар бодлого ойлгоход асуудалгүй гэвэл codechef, codeforces- сайтаас бодоод яваарай. Доорх кодыг хэрхэн ажлуулах боломжтой вэ гэвэл ideone гээд online tool байгаа ба үүнийг ашиглаж болно....