Dragons
Kirito must defeat all \(n\) dragons on a level of a game. His strength is initially \(s\). The \(i\)-th dragon has strength \(x_i\).
- If Kirito fights the \(i\)-th dragon and his strength is not greater than \(x_i\), he loses.
- Otherwise he defeats the dragon, and his strength increases by \(y_i\).
Kirito can fight the dragons in any order. Determine whether he can defeat all dragons without a single loss.
Constraints:
- \(1 \le s \le 10^4\), \(1 \le n \le 10^3\)
- \(1 \le x_i \le 10^4\), \(0 \le y_i \le 10^4\)
Input:
- First line: two integers \(s\) and \(n\).
- Next \(n\) lines: two integers \(x_i\) and \(y_i\) — the strength of the \(i\)-th dragon and the bonus for defeating it.
Output:
YESif Kirito can defeat all dragons, andNOotherwise.
Example:
Input:
2 2
1 99
100 0
Output:
YES
(Kirito defeats the first dragon, his strength becomes \(2 + 99 = 101\), and then he defeats the second dragon.)
Solution
Kirito’s strength never decreases, so it is always best to fight the weakest remaining dragon first: if Kirito cannot defeat the weakest remaining dragon, he cannot defeat any other remaining dragon either.
We store each dragon in a struct with two members, sort the dragons by strength with a custom comparator, and fight them in this order. If some dragon has strength at least \(s\), the answer is NO.
Sorting takes \(O(n \log n)\) time.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Dragon {
int strength;
int bonus;
};
bool weaker(Dragon a, Dragon b) {
return a.strength < b.strength;
}
int main() {
int s, n;
cin >> s >> n;
vector<Dragon> dragons(n);
for (int i = 0; i < n; i++) {
cin >> dragons[i].strength >> dragons[i].bonus;
}
sort(dragons.begin(), dragons.end(), weaker);
for (int i = 0; i < n; i++) {
if (s <= dragons[i].strength) {
cout << "NO\n";
return 0;
}
s += dragons[i].bonus;
}
cout << "YES\n";
}