Learn C++ STL

Lesson 6 of 9 · priority_queue: The Biggest One Comes Out First

Module 7 · priority_queue: The Biggest One Comes Out First

CP and Interview Pack: priority_queue Patterns, Questions and the Bug Gallery

ProReading

Codeforces Round 723 (Div. 2), held on 28 May 2021, had problem 1526C2, "Potions (Hard Version)". You pass a row of potions from left to right, drinking or skipping each, and want to drink as many as you can. Each potion changes your health by its number, which can be negative, and health starts at 0 and must never drop below 0. Bob drinks whenever his health stays at 0 or more. Amara drinks them all and takes back the worst one when she must, and her answer is pattern 1 below.

Checking what this lesson needs for you…

What is inside CP and Interview Pack: priority_queue Patterns, Questions and the Bug Gallery

  1. Pattern 1: greedy with regret
  2. Pattern 2: Huffman coding
  3. Pattern 3: Dijkstra's shape
  4. Pattern 4: lazy deletion
  5. Pattern 5: the k smallest sums of pairs
  6. Ten interview questions, with model answers