洛谷链接

题目描述

在小Z的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小Z刚刷完CodeChef，准备出来逛逛。
机房一条街有 n 个机房，第 i 个机房的坐标为 xi ，小Z的家坐标为 0。小Z在街上移动的速度为1，即从 x1 到 x2 所耗费的时间为 |x1 − x2|。 每个机房的学生数量不同，ACM 题目水平也良莠不齐。小Z到达第 i 个机房后，可以花 ti 的时间想题，然后瞬间 AK；当然，也可以过机房而不入。
小Z现在只有 m 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。

输入格式

第一行包含两个整数 n，m。
接下来 n 行，每行包含两个整数 xi，ti 。

输出格式

第一行包含一个整数，表示小Z最多能 AK 的机房数量。

输入

2 10
1 100
5 5

输出

1
思路：看见这道题，再一看标签，就明白是贪心，但有一个问题，就是如何保证选取哪一个，可以想到每一次都用堆记录，如果当前的时间超过了m，那么就减去最大的那一个任务的用时，注意：一定要先添加入堆，再取出最大的值，因为有可能添加的值最大，这样就减少了判断。详情看代码；

代码

#include<queue>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;

struct lx {
	int x, t;
}a[100005];

bool cmp(lx l, lx r) {
	return l.x < r.x;
}

int Min(int x, int y) { return x < y ? x : y; }

priority_queue<int> q;

signed main() {
	int n, m, sum = 0, ans = 0, now = 0;
	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i ++) {
		scanf("%lld %lld", &a[i].x, &a[i].t);
	} sort(a + 1, a + 1 + n, cmp);//按距离排序
	for(int i = 1; i <= n; i ++) {
		sum += a[i].x - a[i - 1].x + a[i].t;//加上两个点的距离与当前任务的时间
		q.push(a[i].t); ans ++;//一定要先加
		if(sum > m) {
			ans --; sum -= q.top();
			q.pop();//弹出最大的任务
		}
	} printf("%lld", ans);
}