F1. Complete the Projects (easy version) - 题解

比赛与标签

比赛: Codeforces Round 579 (Div. 3) 标签: greedy, *2100 难度: *2100

嘿，主人！来看这道题怎么解喵~

这道题是说，我们可爱的 freelancer Polycarp酱有一些初始评分r，要去完成n个项目。每个项目都有一个要求：你需要至少有a_i的评分才能开始做。完成之后呢，你的评分会变化b_i（b_i可能是正数也可能是负数哦）。

最重要的是，在整个过程中，Polycarp酱的评分绝对不能掉到0以下，不然就没人信赖他了！我们的任务就是判断，是否存在一个完成所有项目的顺序，可以满足所有的要求。如果可以，就输出"YES"，不然就输出"NO"，很简单对吧~？

贪心的小猫爪，一抓就中！

这是一道典型的贪心问题哦！一看到要找一个“是否存在满足条件的顺序”，我们就可以往贪心的方向想一想呐。关键在于，我们每一步都做出当前看起来最优的选择，最后就能得到全局最优解。

那，什么才是“最优的选择”呢？我们可以把所有项目分成两类来考虑，这样思路就清晰多啦！

评分会增加的项目 (b_i >= 0): 这些是“好”项目！它们能提升我们的评分，让我们更有资本去挑战那些要求高或者会扣分的项目。对于这类项目，我们的策略当然是越早做越好！那在这些好项目之间，应该按什么顺序呢？当然是先做那些要求评分低 (a_i小) 的项目啦。你想呀，如果我们连要求最低的项目都做不了，那要求更高的就更没戏了，对不对？所以，我们把这些项目按照 a_i 从小到大排序，然后依次完成。这样可以最快地积累评分，为后续的项目铺路！
评分会减少的项目 (b_i < 0): 这些是“坏”项目，有点小危险~ 它们会消耗我们的评分。对于这类项目，我们应该在自己评分尽可能高的时候再去做，这样才能承受住评分的下降。所以，一个很自然的想法是：先把所有能加分的项目都做完，把评分刷到最高，然后再来处理这些会减分的项目。

那这些减分项目之间，又该按什么顺序呢？这可是这道题最关键、最有趣的地方了喵！

假设我们现在有两个减分项目X (a_x, b_x) 和 Y (a_y, b_y)。我们应该先做哪个呢？我们来想一下，哪个项目更“危险”？一个项目完成后，我们的评分会下降。如果下降后，我们的评分太低，就可能无法满足下一个项目的起始要求了。所以，我们应该优先做那些相对“安全”的项目。什么样的项目是安全的呢？就是那些即使完成了，我们的评分也不会掉得太惨的项目。

考虑一个项目i，如果我们以刚好满足要求的评分a_i开始，完成后的评分就是a_i + b_i。这个值可以看作是完成这个项目后，我们能达到的最低评分状态。这个值越大，说明这个项目完成后我们的处境越安全。

所以，我们的策略就出来啦：对于所有减分项目，我们按照 a_i + b_i 的值从大到小排序！先做 a_i + b_i 大的，把那些做完后评分掉得最狠的、最“危险”的项目留到最后。那时候我们的评分已经被前面相对安全的项目消耗了一部分，但因为我们是按最安全的顺序来的，所以这是我们能拥有的最高评分状态了。

总结一下我们的贪心策略喵~：

把项目分成两组：加分项目 inc (b_i >= 0) 和减分项目 dec (b_i < 0)。
先处理 inc 组：按 a_i 从小到大排序，依次完成。过程中如果评分不够，就直接失败。
再处理 dec 组：按 a_i + b_i 从大到小排序，依次完成。过程中如果评分不够，或者完成后评分小于0，就失败。
如果所有项目都能顺利完成，那就是成功啦！

代码实现给你看，喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    // 用两个vector来分别存储加分和减分的项目，喵~
    vector<pair<int, int>> inc, dec;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (b >= 0) {
            // b >= 0 的是好项目，放到inc组
            inc.push_back({a, b});
        } else {
            // b < 0 的是坏项目，放到dec组
            dec.push_back({a, b});
        }
    }

    // --- 第一步：处理加分项目 ---
    // 按要求评分 a_i (pair的第一个元素) 从小到大排序
    sort(inc.begin(), inc.end());

    for (auto &p : inc) {
        // 如果当前评分连要求都达不到，那就没办法啦
        if (r < p.first) {
            cout << "NO" << endl;
            return 0;
        }
        // 成功完成，评分增加！
        r += p.second;
    }

    // --- 第二步：处理减分项目 ---
    // 使用lambda表达式自定义排序规则，按 a_i + b_i 从大到小排序
    sort(dec.begin(), dec.end(), [](const pair<int, int> &x, const pair<int, int> &y) {
        // x.first + x.second > y.first + y.second 意味着x更“安全”，优先做x
        return x.first + x.second > y.first + y.second;
    });

    for (auto &p : dec) {
        // 同样，检查评分是否足够开始项目
        if (r < p.first) {
            cout << "NO" << endl;
            return 0;
        }
        // 完成项目，评分减少
        r += p.second;
    }

    // --- 最后检查 ---
    // 所有项目都完成了，只要最后评分不小于0，就说明整个过程都没问题
    // 因为减分项目的 b_i 都是负数，如果最后 r >= 0，那么中间的 r 一定也大于等于最后的 r，所以肯定也 >= 0
    if (r < 0) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }

    return 0;
}

复杂度分析时间到！

时间复杂度: O(n log n) 的说。
- 我们需要遍历一次所有项目来把它们分组，这是 O(n)。
- 然后我们对两个组分别进行了排序。假设加分项目有 k 个，减分项目有 n-k 个，排序的时间分别是 O(k log k) 和 O((n-k) log (n-k))。在最坏的情况下，所有项目都在一个组里，所以排序的复杂度是 O(n log n)。
- 最后遍历两个排好序的组，又是 O(n)。
- 所以总的时间复杂度由排序决定，是 O(n log n) 呐。
空间复杂度: O(n) 的说。
- 我们创建了两个 vector，inc 和 dec，来存储所有的项目。它们加起来总共存储了 n 个项目，所以空间复杂度是 O(n)。

知识点与总结喵~

这道题真是贪心算法的一个绝佳例子！主人你看，我们通过几个简单的步骤就解决了问题：

分类讨论: 解决复杂问题的一个好方法就是把它分解成几个更简单的小问题。这里我们把项目分成“加分”和“减分”两类，策略一下子就清晰了。
贪心策略的选择: 针对不同类别的问题，要找到最合适的贪心标准。
- 对于“增益型”任务（加分项目），通常先做成本低（要求评分a_i低）的。
- 对于“损耗型”任务（减分项目），策略就比较微妙了。这里我们选择先做风险小（a_i + b_i 值大）的，把最大的风险留到我们最有能力应对的时候。
排序是贪心的好朋友: 很多贪心算法的实现都离不开排序。想清楚按什么标准排序，问题就解决了一大半！
编程技巧: 代码里用到的 std::sort 配合自定义的 lambda 函数，是C++里实现自定义排序非常方便的写法，主人可以多练习一下哦！

希望这篇题解能帮到你！只要思路对了，代码实现起来就顺风顺水啦。一起加油，变得更强喵~！

F1. Complete the Projects (easy version) - 题解 ​

比赛与标签 ​

嘿，主人！来看这道题怎么解喵~ ​

贪心的小猫爪，一抓就中！ ​

代码实现给你看，喵~ ​

复杂度分析时间到！ ​

知识点与总结喵~ ​