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

· · 题解

Background

算法：二分答案、贪心。

首先理解题意，共有三个重要的信息，我们可以理解为：门槛、花费、报酬。其中报酬的值为门槛减去花费。

Solution

简单思考，我们可以得出贪心策略：

  1. 先完成回报多的任务，这样才能留下更多给回报少的。

  2. 若回报相同，先完成门槛高的，不然后面无法完成。

由此，我们可以用二分答案：

  1. 直接枚举希望的最小值，检验是否满足全部任务都能完成。

  2. 若可以，找更小的满足值；若不可以，找较大的可能值。

Code

细节可以看注释。

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

class Quick_IO
{
  public:
    template<typename T>
    void read(T &r)
    {
        T x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
        r = x * f;
    }
    template<typename T, typename... Args>
    void read(T &tmp, Args &... tmps)
    {
        read(tmp);
        read(tmps...);
    }
} io;

int n, M;
struct node //门槛，花费，回报
{
    int need, cost, reward;
} a[N];
bool operator < (node x, node y)    //排序
{
    if (x.reward == y.reward) return x.need > y.need; //回报一样的话先完成门槛高的
    return x.reward > y.reward; //先完成回报多的
}

bool Judge(int aim) //判断
{
    for (int i = 1; i <= n; i++)
    {
        //注意二分初始区间已经排除了买不起的可能，因此不用再if
        if (aim < a[i].need) return 0;
        aim -= a[i].cost;
    }
    return 1;
}

signed main()
{
    io.read(n);
    for (int i = 1; i <= n; i++)
    {
        io.read(a[i].need, a[i].cost);
        a[i].reward = a[i].need - a[i].cost;
        M += a[i].cost;
    }
    sort(a + 1, a + 1 + n);

    int L = M, R = 2e9, mid, ans = 2e9;
    while (L <= R)  //二分答案
    {
        mid = L + (R - L) / 2;
        if (Judge(mid)) ans = mid, R = mid - 1;
        else L = mid + 1;
    }
    cout << ans;
}