【GOJ 3038】逛餐馆

传送门

解析

显然我们只会往一个方向走，不会回头（回头一定浪费时间）。那我们将所有餐馆序。

那我们不妨枚举我们能走到最远的餐馆，假设我们枚举我们走到第 (i)个餐馆（排完序之后）。
那么我们就是在 (1) ~ (i) 餐馆中寻若干个餐馆，使他们和不超过 (m-x_i)，然后求最多的个数即可。那显然就是在 (1) ~ (i) 餐馆中按照 (t_i) 从小到大排序，然后不断累加直至超过 (m-x_i) 的餐馆个数。

这个经典題目用优先队列来维护即可。

我们维护一个大根堆，这个堆里面维护 (1) ~ (i) 所有餐馆中，最小的若干个餐馆，并且他们和 (le m-x_i)。

那我们从 (1) 到 (n) 枚举 (i) ，每次执行三个操作：

1. 把 (t_i) 加进堆里面。
2. 若堆中元素之和大于 (m-x_i)，则不断弹出堆顶元素直到总和小于等于 (m-x_i)。
3. 堆的大小就是我们能吃的餐馆的个数，用这个更新答案。

时间复杂度为 (O(n log_2n))。

代码

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL N=1e5+5;
struct jvav {
	LL x,t;
	void read() {
		scanf("%lld %lld",&x,&t);
	}
	bool operator<(const jvav &bee) const {
		return x<bee.x;
	}
} a[N];
priority_queue<LL> q;
int main() {
	LL n,m;
	scanf("%lld %lld",&n,&m);
	for(LL i=1; i<=n; i++) {
		a[i].read();
	}
	sort(a+1,a+n+1);
	LL sum=0,ans=0;
	for(LL i=1; i<=n; i++) {
		q.push(a[i].t),sum+=a[i].t;
		while(q.size()&&sum>m-a[i].x) {
			sum-=q.top(),q.pop();
		}
		if(ans<q.size()) {
			ans=q.size();
		}
	}
	printf("%lld",ans);
	return 0;
}