[codeforces]230A DRAGONS – Sort with custom comparator

Problem statement is here: http://codeforces.com/contest/230/problem/A

The problem is not difficult, what makes it even easier it that even O(n^2) solution is accepted by the judge.

If you consider each Dragon as a struct of strength that it possesses and the bonus it gives then the problem becomes a matter of sorting Dragons that can be killed by the player’s initial strength. I have sorted using a custom comparator which makes life a lot easy. Here is the code:

#include <bits/stdc++.h>

struct Dragon {
  int strength;
  int bonus;
  Dragon(int strength, int bonus) : strength(strength), bonus(bonus) {}
};

bool comparator(Dragon i, Dragon j) {
  return i.strength < j.strength;
}

int main() {
  int player_strength;
  int num_dragons;

  std::cin >> player_strength >> num_dragons;

  std::vector<Dragon> dragons;

  for (int i = 0; i < num_dragons; i++) {
    int strength, bonus;
    std::cin >> strength >> bonus;
    dragons.push_back(Dragon(strength, bonus));
  }

  std::sort(dragons.begin(), dragons.end(), comparator);

  for(Dragon dragon : dragons) {
    if(dragon.strength < player_strength) {
      player_strength+=dragon.bonus;
    }
    else {
      std::cout<<"NO";
      return 0;
    }
  }

  std::cout<<"YES";

  return 0;
}

Please let me know in comments if you have found a more optimal way to solve the problem. Cheers!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.