自动搬运

查看原文

来自洛谷，原作者为

	FJ_EYoungOneC 这个人很勤快，但是他并不想留下什么

搬运于2025-08-24 21:18:30，当前版本为作者最后更新于2025-04-05 15:11:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

我们先来考虑第一个问题：假设任务次序已经确认，该如何求解所需的最小能量？

很明显，假设能量 $x$ 可以完成所有任务，那么能量大于 $x$ 时一定可以。假设能量 $y$ 不能完成所有任务，那么小于 $x$ 时一定也不可以。举有单调性，可以使用二分求解。

第二个问题：如何确定任务次序，使得所需能量最小？

策略如下：算出所有任务的 $d = x - y$ 表示以 $x$ 能量启动任务剩余的能量，按照 $d$ 从大到小进行排序。

证明如下：

设有任务一 $x_1, y_1, d_1$ 排在任务二 $x_2, y_2, d_2$ 的前面（$d = x - y$）。

那么对于完成任务一所需最初能量为 $x_1$，完成任务二的所需最初能量为 $x_2 - (x_1 - y_1)$，总消耗能量为 $y_1+y_2$。

所需最初能量为 $\max(x_1, x_2-d_1)$。

交换任务一和任务二的执行顺序，那么所需最初能量为 $\max(x_2, x_1-d_2)$，总消耗能量任为 $y_1+y_2$。

总消耗能量相同，我们来讨论一下最初能量的大小比较。

若 $d1 ≥ d2$（即 $x_1-y_1 \geq x_2-y_2$）可得：$x_1 + y_2 \geq x_2 + y_1$。

比较两种情况：

1. 顺序执行（任务一 $\rightarrow$ 任务二）：所需最小能量 $E_1 = \max(x_1, x_2 + y_1)$
2. 逆序执行（任务二 $\rightarrow$ 任务一）：所需最小能量 $E_2 = \max(x_2, x_1 + y_2)$

分情况讨论：

• 若 $x_1 \geq x_2 + y_1$，则：
  • $E_1 = x_1$
  • $E_2 = \max(x_2, x_1 + y_2) = x_1 + y_2$ （因为 $x_1 + y_2 ≥ x_2 + y_1 \geq x_2$）
  • ∵ $x_1 \leq x_1 + y_2$ ∴ $E_1\geq E_2$
• 若 $x_1 < x_2 + y_1$，则：
  • $E_1 = x_2 + y_1$
  • $E_2 = \max(x_2, x_1 + y_2) = x_1 + y_2$（因为 $x_1 + y_2 ≥ x_2 + y_1 ≥ x_2$）
  • ∵ $x_2 + y_1 \leq x_1 + y_2$ ∴ $E_1 \leq E_2$

结论： 当 $d_1 \leq d_2$ 时，顺序执行（任务一在前）所需初始能量 $\leq$ 逆序执行，因此按 $d$ 值降序排列最优。

AC_Code

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Node
{
    int a, b, d;
    bool operator< (const Node &t) const
    {
        return d > t.d;
    }
}q[N];

bool check(int x)
{
    for (int i = 0; i < n; ++ i )
        if (x < q[i].a)
            return false;
        else
            x -= q[i].b;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; ++ i )
    {
        int a, b;
        cin >> a >> b;
        q[i] = {a, b, a - b};
    }

    sort(q, q + n);

    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }

    cout << l << endl;
    
    return 0;
}