题意简述

有 $N$ 个节点，每个节点有攻击门槛 $A_i$ 和战后恢复 $B_i$。

攻击第 $i$ 个节点前，当前精力必须满足：

$$cur \ge A_i$$

攻击后精力变化为：

$$cur \leftarrow cur - A_i + B_i$$

可以任意安排攻击顺序，要求任意时刻精力不低于 $0$。问初始精力至少是多少。

---

核心思路

每个节点的净收益为：

$$B_i - A_i$$

如果 $B_i - A_i \ge 0$，也就是 $A_i \le B_i$，说明打完后精力不会减少，甚至会变多，称为正收益节点。

如果 $B_i - A_i < 0$，也就是 $A_i > B_i$，说明打完后精力会减少，称为负收益节点。

显然：

1. 正收益节点应该尽量先打，因为它们会让精力变多；
2. 负收益节点应该尽量后打，因为它们会让精力变少；
3. 正收益节点内部，门槛低的先打；
4. 负收益节点内部，恢复值 $B_i$ 大的先打。

于是排序规则为：

• 先排正收益节点：$A_i \le B_i$
  • 按 $A_i$ 升序排序
• 后排负收益节点：$A_i > B_i$
  • 按 $B_i$ 降序排序
  • 如果 $B_i$ 相同，按 $A_i$ 升序排序

---

贪心正确性说明

1. 正收益节点一定放在负收益节点前面

假设有一个负收益节点 $j$ 排在正收益节点 $i$ 前面。

交换它们：

• 原来先打 $j$，精力减少，再打 $i$；
• 交换后先打 $i$，精力不减少甚至增加，再打 $j$。

交换后，打 $j$ 之前的精力只会更高，所以不会更难满足门槛。

因此所有正收益节点都应该排在负收益节点前面。

---

2. 正收益节点内部按 $A_i$ 升序

两个正收益节点 $i,j$，若：

$$A_i > A_j$$

如果先打 $i$，则一开始就需要至少 $A_i$ 的精力。

如果先打 $j$，因为 $A_j$ 更小，更容易满足，而且打完后精力还会增加，再去打 $i$ 会更轻松。

所以正收益节点应按门槛 $A_i$ 从小到大排序。

---

3. 负收益节点内部按 $B_i$ 降序

两个负收益节点 $i,j$，假设：

$$B_i > B_j$$

如果先打 $i$，打完虽然会消耗精力，但会恢复更多 $B_i$，留给后面节点更多精力。

如果先打 $j$，恢复的精力更少，后面打 $i$ 时压力更大。

所以负收益节点应按恢复值 $B_i$ 从大到小排序。

---

如何计算最少初始精力

排序后，我们按最优顺序模拟。

设：

• cur 表示当前精力；
• need 表示需要额外补充的初始精力。

初始令：

$$cur = 0,\quad need = 0$$

依次处理每个节点：

如果当前精力不足以攻击：

$$cur < A_i$$

那么就需要补充：

$$need += A_i - cur$$

并且把当前精力补到 $A_i$：

$$cur = A_i$$

然后攻击该节点，精力变化：

$$cur += B_i - A_i$$

最终 need 就是最少需要的初始精力。

为什么这样是对的？

因为每次当前精力不够时，缺多少就必须在初始精力里多补多少。
最后累计出来的 need，就是整个过程中所有缺口的最大值总和，也就是最小初始精力。

---

时间复杂度

排序时间复杂度：

$$O(N \log N)$$

模拟时间复杂度：

$$O(N)$$

总时间复杂度：

$$O(N \log N)$$

空间复杂度：

$$O(N)$$

---

参考代码

注：Panda写

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

const int N=1e5+5;

struct Task{
    int a,b;
};

int n;
Task a[N];

bool cmp(Task x,Task y){
    bool chka=(x.a<=x.b);//x是否为正收益关卡
    bool chkb=(y.a<=y.b);//y是否为正收益关卡
    if(chka!=chkb) return chka>chkb;
    if(chka) return x.a<y.a;//正收益关卡按门槛升序排列
    else{
        if(x.b!=y.b) return x.b>y.b;//负收益关卡按恢复值降序排列
        return x.a<y.a;
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].a>>a[i].b;

    sort(a+1,a+n+1,cmp);

    int m=0,need=0;//m为当前生命值，need为需要补充补充的初始生命值
    for(int i=1;i<=n;i++){
        if(m<a[i].a){
            need+=a[i].a-m;
            m+=a[i].a-m;
        }
        m+=a[i].b-a[i].a;
    }
    cout<<need<<endl;
    return 0;
}