F1. 完成所有项目（简单版本）

问题重述

Polycarp 当前评分为 $r$。有 $n$ 个项目，第 $i$ 个项目需要评分至少 $a_i$ 才能开始，完成后评分变化为 $b_i$（可正可负）。评分在任何时候不能低于 $0$。
问：是否存在一种顺序，使得所有项目都能完成？

• $n \le 100$，$r \le 30000$
• $a_i \le 30000$，$-300 \le b_i \le 300$

---

核心思路

将项目分为两类：

• 加分项目：$b_i \ge 0$
• 减分项目：$b_i < 0$

第一步：处理加分项目

对于 $b_i \ge 0$ 的项目，显然应该按照 $a_i$ 从小到大排序（先做要求低的，再做要求高的）。
依次检查当前评分是否 $\ge a_i$，若是则完成并更新 $r = r + b_i$；否则直接输出 "NO"。

第二步：处理减分项目

对于 $b_i < 0$ 的项目，情况更复杂。
关键观察：完成一个减分项目后评分会下降，所以需要合理安排顺序。

---

减分项目的贪心策略

引理

将所有减分项目按 $(a_i + b_i)$ 从大到小排序，然后依次尝试完成，是最优的。

证明思路（交换论证）

考虑两个相邻的减分项目 $i$ 和 $j$（$b_i, b_j < 0$）。
假设当前评分为 $r$，先做 $i$ 再做 $j$ 可行的条件是：

$$r \ge a_i,\quad r + b_i \ge a_j$$

先做 $j$ 再做 $i$ 可行的条件是：

$$r \ge a_j,\quad r + b_j \ge a_i$$

我们希望选择约束更弱的顺序。比较两个条件中的关键项：

• 先 $i$ 后 $j$ 要求 $r \ge \max(a_i, a_j - b_i)$
• 先 $j$ 后 $i$ 要求 $r \ge \max(a_j, a_i - b_j)$

注意到 $a_j - b_i > a_j$，$a_i - b_j > a_i$，所以只需比较 $a_j - b_i$ 和 $a_i - b_j$。

计算：

$$(a_j - b_i) < (a_i - b_j) \iff a_j + b_j < a_i + b_i $$

因此，当 $a_i + b_i > a_j + b_j$ 时，先做 $i$ 再 $j$ 的条件更弱（更容易满足）。
所以应该按 $a_i + b_i$ 从大到小排序。

---

处理边界条件

对于减分项目，还有一个细节：
为了保证完成项目后评分非负，在尝试完成前需要额外检查：

$$r \ge \max(a_i, -b_i)$$

因为如果 $r \ge -b_i$，则完成后的评分 $r + b_i \ge 0$。
所以实际操作中，可将 $a_i$ 更新为 $\max(a_i, -b_i)$，再按 $a_i + b_i$ 排序。

---

算法步骤

1. 读入 $n, r$
2. 将项目分为两组：
   • pos：$b_i \ge 0$，按 $a_i$ 升序排序
   • neg：$b_i < 0$，按 $(a_i + b_i)$ 降序排序（或按 $a_i$ 升序？需注意）
3. 处理 pos 组：依次判断 $r \ge a_i$，更新 $r = r + b_i$
4. 处理 neg 组：依次判断 $r \ge a_i$ 且 $r + b_i \ge 0$，更新 $r = r + b_i$
5. 若所有项目都完成，输出 "YES"，否则 "NO"

---

时间复杂度

排序 $O(n \log n)$，遍历 $O(n)$，总体 $O(n \log n)$。

---

示例解析

示例 1

3 4
4 6
10 -2
8 -1

• 加分项目：(4,6)，按 $a$ 排序后唯一，$r=4 \ge 4$ → $r=10$
• 减分项目：(10,-2), (8,-1)
  计算 $a+b$：$10-2=8$，$8-1=7$，按降序：先 (10,-2) 后 (8,-1)
  当前 $r=10$：完成 (10,-2) → $r=8$
  完成 (8,-1) → $r=7$
  全部完成 → "YES"

---

标程代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, r;
    cin >> n >> r;
    
    vector<pair<int, int>> pos, neg;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        if (b >= 0) {
            pos.push_back({a, b});
        } else {
            neg.push_back({a, b});
        }
    }
    
    // 处理加分项目
    sort(pos.begin(), pos.end());
    for (auto &p : pos) {
        if (r < p.first) {
            cout << "NO" << endl;
            return 0;
        }
        r += p.second;
    }
    
    // 处理减分项目：按 a+b 降序排序
    sort(neg.begin(), neg.end(), [](pair<int, int> x, pair<int, int> y) {
        return x.first + x.second > y.first + y.second;
    });
    
    for (auto &p : neg) {
        if (r < p.first) {
            cout << "NO" << endl;
            return 0;
        }
        r += p.second;
        if (r < 0) {
            cout << "NO" << endl;
            return 0;
        }
    }
    
    cout << "YES" << endl;
    return 0;
}

---

易错点

1. 减分项目的排序依据是 $a_i + b_i$ 降序，不是 $a_i$ 升序
2. 完成减分项目后要检查 $r$ 是否 $\ge 0$
3. $a_i$ 可能小于 $-b_i$，此时实际要求是 $r \ge -b_i$（但标程中直接用 $a_i$ 判断，因为 $a_i$ 已经保证了这一点？需要确认）