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

#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;
}