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

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

描述：

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

你接到

n

个任务，可以按任意顺序完成。

对于每个任务都有其对应的底线

x

和消耗

y

，且保证

x \ge y

。启动第

i

个任务前，当前能量必须

\ge x[i]

；完成第

i

个任务后会消耗

y[i]

能量。

你需要找出一个最小初始值

E

，确保这

n

个任务在某种排序下均能完成。

算法：

二分求出最小初始值

E

，使其能完成这

n

个任务。

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

90

分。

CPP

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

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

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

我们假设只有

2

个任务，分别用

A

与

B

表示。

更改后的代码如下。

CPP

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:

CPP

#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;//好习惯。
}

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

文章操作

描述：

算法：

AC Code:

相关推荐

评论

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