dragons

Dragons

Codeforces easy

يجب على كيريتو أن يهزم كل التنانين الـ \(n\) في مرحلة من لعبة. قوته في البداية \(s\). قوة التنين رقم \(i\) هي \(x_i\).

إذا قاتل كيريتو التنين رقم \(i\) وكانت قوته لا تزيد عن \(x_i\)، فإنه يخسر.
وإلا فإنه يهزم التنين، وتزيد قوته بمقدار \(y_i\).

يمكن لكيريتو أن يقاتل التنانين بأي ترتيب. حدّد هل يستطيع أن يهزم كل التنانين دون أي خسارة.

القيود:

\(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\)

الإدخال:

السطر الأول: عددان صحيحان \(s\) و \(n\).
الأسطر الـ \(n\) التالية: عددان صحيحان \(x_i\) و \(y_i\) — قوة التنين رقم \(i\) والزيادة عند هزيمته.

المخرجات:

YES إذا استطاع كيريتو أن يهزم كل التنانين، و NO في غير ذلك.

مثال:

الإدخال:

2 2
1 99
100 0

المخرجات:

YES

(يهزم كيريتو التنين الأول، فتصبح قوته \(2 + 99 = 101\)، ثم يهزم التنين الثاني.)

الحل

قوة كيريتو لا تنقص أبدًا، لذلك الأفضل دائمًا أن يقاتل أضعف تنين متبقٍّ أولًا: إذا لم يستطع كيريتو هزيمة أضعف تنين متبقٍّ، فلن يستطيع هزيمة أي تنين متبقٍّ آخر.

نخزّن كل تنين في struct له عضوان، ونرتّب التنانين حسب القوة باستخدام دالة مقارنة مخصّصة، ثم نقاتلها بهذا الترتيب. إذا كانت قوة تنين ما أكبر من أو تساوي \(s\)، فالجواب NO.

يستغرق الترتيب \(O(n \log n)\).

#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";
}