#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/cpp/vectors-stl-basics/dragons-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/cpp/vectors-stl-basics/dragons-implementation

Repovive

Dragons - Implementation - Vectors & STL Basics | C++ | Repovive

Repovive.

C++20 sections · 1034 units68h total

Open in Course

Dragons - Implementation

Complete solution


plaintext
function defeat_dragons(s, dragons)
 // dragons is vector of pairs (strength, bonus)
 sort(dragons) // sort by first element (strength)
 current_strength := s
 for each dragon in dragons
 if current_strength > dragon.strength then
 current_strength := current_strength + dragon.bonus
 else
 return "NO"
 return "YES"

The time complexity is $O(n \log n)$ for sorting, where $n$ is the number of dragons.