Решение задачи Драконы с Codeforces

Без пояснения   Просмотров: 36


Кирито застрял на очередном уровне MMORPG, в которую он играет. Чтобы пройти игру дальше, ему нужно победить всех n драконов, которые живут на этом уровне. Как Кирито, так и драконы обладают силой, которая выражается целым числом. В схватке между двумя противниками исход схватки определяется их силой. Изначально сила Кирито равна s.

Если Кирито вступает в схватку с i-ым (1 ≤ i ≤ n) драконом и его сила не больше, чем сила этого дракона xi, то Кирито проигрывает схватку и умирает. Если же сила Кирито больше, чем сила дракона, то он побеждает дракона и получает бонус — его сила увеличивается на yi.

Кирито может сражаться с драконами в произвольном порядке. Определите, сможет ли он пройти на следующий уровень игры, то есть победить всех драконов, не умирая ни разу.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int s, n, k = 0;
    cin >> s >> n;
    vector<int> a(n);
    vector<int> b(n);
    for(int i = 0; i < a.size(); ++i)
        cin >> a[i] >> b[i];
    for(int i = 0; i < a.size() - 1; ++i)
        for(int j = i + 1; j < a.size(); ++j)
            if(a[i] > a[j]){
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    for(int i = 0; i < a.size(); ++i)
        if(a[i] < s){
            s += b[i];
            ++k;
        }
    if(k == a.size())
        cout << "YES";
    else
        cout << "NO";

    return 0;
}
//    7 7
//    1 2 3 4 5 6 8
//    9 8 7 6 5 4 3

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться