题目描述
在小 X 的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小 X 刚刷完
CodeChef，准备出来逛逛。
机房一条街有 n 个机房，第 i 个机房的坐标为 xi，小 X 的家坐标为 0。小 X 在街上移动的速度为
1，即从 x1 到 x2 所耗费的时间为 |x1 − x2|。
每个机房的学生数量不同，ACM 题目水平也良莠不齐。小 X 到达第 i 个机房后，可以花 ti 的时间
想题，然后瞬间 AK；当然，也可以过机房而不入。
小 X 现在只有 m 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多
少个机房 AK，希望你帮帮他。
Input
第一行包含两个整数 n, m。
接下来 n 行，每行包含两个整数 xi, ti。
Output
第一行包含一个整数，表示小 X 最多能 AK 的机房数量。
Example
plan.in
2 10
1 100
5 5
plan.out
1
思路
9见注释0
代码
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
long long m;
struct point
{
long long x,t;
};
point q[100001];
bool cmp(point a,point b)//改变Sort排序顺序(从大到小)
{
return a.x+a.t<b.x+b.t;
}
int main()
{
freopen("plan.in","r",stdin);
freopen("plan.out","w",stdout);
cin >> n >> m;
for(int i=1;i<=n;i++)
scanf("%d %d",&q[i].x,&q[i].t);
sort(q+1,q+1+n,cmp);
q[0].x=0;//起点
for(int i=1;i<=n;i++)//dp
{
if(q[i].x>q[i-1].x) m=m-(q[i].x-q[i-1].x)-q[i].t;
else m=m-q[i].t;
if(m>=0) ans++;
else break;
}
cout << ans << endl;
return 0;
}