Codeforce Dragons

题目描述

思路

这道题的重点是可以自由挑选打龙的顺序，所以可以用vector来存储所有x，y的值，然后进行排序。

代码

C++

#include <iostream>
#include <vector>
#include <algorithm> // for sort
using namespace std;

int main() {
    int s, n;
    cin >> s >> n;

    vector<pair<int, int>> dragons(n); // 每条龙是一个(x, y)的vector

    for (int i = 0; i < n; ++i) {
        cin >> dragons[i].first >> dragons[i].second; // first 是 x，second 是 y
    }

    // 按照龙的强度从小到大排序
    // 默认先按照 pair 的 first 升序排列。如果 first 相等，再按照 second 升序排列
    // begin和end会对所有内容进行排序。
    sort(dragons.begin(), dragons.end());
	
    for (int i = 0; i < n; ++i) {
        if (s > dragons[i].first) {
            s += dragons[i].second; // 赢了，加数值的奖励
        } else {
            cout << "NO" << endl;
            return 0; 
        }
    }

    cout << "YES" << endl;
    return 0;
}

如果是降序的话需要写成

1
2
3

sort(dragons.begin(), dragons.end(), [](pair<int, int> a, pair<int, int> b) {
    return a.first > b.first;
});