反悔贪心

首先很容易想到按照 $B_i$ 排序，因为如果一个物品到了时间限制，那么 $B_i$ 比它小的数都已经选不了了

但是可能这样不是最优的，考虑怎么反悔贪心，即考虑怎么将一个 $B_i$ 较小的物品替换成另一个 $B_i$ 较大的物品，并且使其能装下更多的物品。

记录一个 $sum$ ，表示目前所选的物品的 $A_i$ 的和，也表示打完所选的怪所需的时间。

对于一个物品 $i$ ，若 $sum+A_i \le B_i$ ，则它可以直接加进去。若 $sum+A_i > B_i$ ，考虑替换，选先前选过的中最大的 $A_j$ ，若 $A_i < A_j$ 并且 $sum-A_j+A_i \le B_i$ ，就可以替换，且这样替换一定是最优的。

明显可以用大根堆维护先前选过的最大的 $A_j$

综上所述，有AC代码：

struct Tim_justforsure{
	int a,b;
	friend bool operator < (Tim_justforsure x,Tim_justforsure y){
		return x.b<y.b;
	}
}f[200005];

struct node{
	int num,id;
	friend bool operator < (node x,node y){
		return x.num<y.num;
	} 
};
priority_queue<node> q;

long long sum;
int n,cnt;

int main(){
	n=read();
	for (int i=1;i<=n;i++){
		f[i].a=read();
		f[i].b=read();
	}
	sort(f+1,f+n+1);
	for (int i=1;i<=n;i++){
		if (f[i].a+sum<=f[i].b){
			sum+=f[i].a;
			cnt++;
			q.push((node){f[i].a,i});
			continue;
		}
		int j=q.top().id;
		if (f[j].a>f[i].a && sum-f[j].a+f[i].a<=f[i].b){
			sum=sum-f[j].a+f[i].a;
			q.pop();
			q.push((node){f[i].a,i});
		}
	}
	printf("%d",cnt);
	return 0;
}

依旧是我一直的观点：操作顺序不影响结果时可以钦定顺序化简问题。

考虑最优情况是什么：显然是每一个都可以打。假设当前存在最优情况，最优的构造就是越早结束的越早打，这样保证每个都能打。

那我们的目的就是逼近最优构造，这启发我们按 $B_i$ 升序排序，依次处理每个点。

现在可以贪心的想，处理到一个没超限的点时直接加进去，记录 $ans+=1,len+=A_i$，如果当前点超限了，说明前 $i$ 个点至多有 $ans$ 个合法，为了保证后面的合法点尽可能的多，当前的 $len$ 一定越小越好，若前面的 $max_{a_j}<A_i$ 直接用 $A_i$ 替换掉它。$ans$ 的值必须保持单调递增，所以只替换一个，替换最大的保证 $len$ 最小化。这是一个很常见的反悔思路（想到了CSP2025被我光速秒掉的T1与挂分挂没的T2,我常常追忆过去）

使用堆维护最大值即可，复杂度 $O(nlogn)$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int N=2e5+17;
int n,ans,top,len;
struct node{
	int a,b;
}q[N];priority_queue<int> st;
bool cmp(node A,node B){
	return A.b<B.b;
}
signed main(){
	//freopen("B.in","r",stdin);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> q[i].a >> q[i].b;
	}sort(q+1,q+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(len+q[i].a<=q[i].b){
			st.push(q[i].a);
			len+=q[i].a;
		}else{
			if((q[i].a<st.top())&&(len-st.top()+q[i].a)<=(q[i].b)){
				len-=st.top();len+=q[i].a;
				st.pop();
				st.push(q[i].a);
			}
		}
	}
	cout << st.size();
	return 0;
}

贪心的证明是没有的（不想推式子是这样的），相信后人的智慧，至少我觉得这篇题解在思路上还是很连贯清晰的