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

_Z_YX_ · 2025-05-01 09:01:06 · 题解

按某位大佬的意见进行了补充说明（二分排序方法）。

描述：

题面有点长，在这里帮大家分析一下：

你接到 n 个任务，可以按任意顺序完成。

对于每个任务都有其对应的底线 x 和消耗 y，且保证 x \ge y。启动第 i 个任务前，当前能量必须 \ge x[i]；完成第 i 个任务后会消耗 y[i] 能量。

你需要找出一个最小初始值 E，确保这 n 个任务在某种排序下均能完成。

算法：

二分求出最小初始值 E，使其能完成这 n 个任务。

需要注意的是，排序时的规则。一开始考虑欠缺，直接按任务的启动值从大到小进行了排序，结果只得了 90 分。

bool cmp(node a,node b){
    if(a.x!=b.x)return a.x>b.x;
    return b.y>a.y;
}

显然，这样排序会导致在启动值较小而消耗值很大的情况下，最终无法完成任务。从而使得二分的结果大于正确答案。

为了让各位更好的理解本题的关键——排序方法，以下进行详细的图文结合说明。

我们假设只有 2 个任务，分别用 A 与 B 表示。

更改后的代码如下。

bool cmp(node a,node b){
    if(a.x-a.y!=b.x-b.y)return a.x-a.y>b.x-b.y;
    return b.x>a.x;
}

AC Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,l,r;
struct node{
  int x,y;
}a[N];
bool cmp(node a,node b){//重点！！！
    if(a.x-a.y!=b.x-b.y)return a.x-a.y>b.x-b.y;
    return b.x>a.x;
}
int check(int x){//判断初始值为x时，是否能完成所有任务。
    for(int i=1;i<=n;i++){
        if(x>=a[i].x)x-=a[i].y;
        else return 0;
    }
    return 1;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i].x,&a[i].y);
        r+=a[i].x+a[i].y;//将r赋为最大值。
    }
    sort(a+1,a+n+1,cmp);//关键！！！
    while(l<=r){//二分求最小初始值。
        int mid=(l+r)>>1;
        if(check(mid))r=mid-1;
        else l=mid+1;
    }
    printf("%lld",l);//输出答案。
    return 0;//好习惯。
}