题解：B4304 [蓝桥杯青少年组省赛 2024] 通关游戏的最少能量值

· · 题解

解题思路

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

很明显，假设能量 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)

分情况讨论：

结论： 当 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;
}