题目描述

又是一年秋季时，陶陶家的苹果树结了 n 个果子。陶陶又跑去摘苹果，这次他有一个 a 公分的椅子。当他手够不着时，他会站到椅子上再试试。

这次与 NOIp2005 普及组第一题不同的是：陶陶之前搬凳子，力气只剩下 s 了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在 s<0 之前最多能摘到多少个苹果。

现在已知 n 个苹果到达地上的高度 xi​，椅子的高度 a，陶陶手伸直的最大长度 b，陶陶所剩的力气 s，陶陶摘一个苹果需要的力气 yi​，求陶陶最多能摘到多少个苹果。

输入格式

第 1 行：两个数 苹果数 n，力气 s。

第 2 行：两个数 椅子的高度 a，陶陶手伸直的最大长度 b。

第 3 行~第 3+n−1 行：每行两个数 苹果高度 xi​，摘这个苹果需要的力气 yi​。

输出格式

只有一个整数，表示陶陶最多能摘到的苹果数。

输入输出样例

输入 

8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2

输出 

4

说明/提示

对于 100% 的数据，n≤5000, a≤50, b≤200, s≤1000, xi​≤280, yi​≤100。

代码

无注释版

#include<bits/stdc++.h>
using namespace std;
struct app{
	int x,y;
}t[5020];
bool cmp(app p,app q){
	if(p.y==q.y) return p.x<q.x;
	return p.y<q.y;
}
int main(){
	int n,s;
	cin>>n>>s;
	int a,b;
	cin>>a>>b;
	for(int i=0;i<n;i++){
		cin>>t[i].x>>t[i].y;
	}
	sort(t,t+n,cmp);
	int cnt=0;
	for(int i=0;i<n;i++){
		if(t[i].x<=b+a&&s>=t[i].y){
			cnt++;
			s-=t[i].y;
		}
	}
	cout<<cnt<<"\n";
} 

有注释版 

#include<bits/stdc++.h> // 包含标准库头文件
using namespace std;    // 使用标准命名空间

// 定义结构体app，表示苹果的属性
struct app {
    int x, y; // x为苹果高度，y为摘苹果需要的力气
} t[5020];    // 定义数组t，最多存储5020个苹果的信息

// 定义比较函数cmp，用于排序
bool cmp(app p, app q) {
    if (p.y == q.y)     // 如果两个苹果需要的力气相同
        return p.x < q.x; // 则按苹果高度升序排序
    return p.y < q.y;    // 否则按摘苹果需要的力气升序排序
}

int main() {
    int n, s; // n为苹果数，s为剩余力气
    cin >> n >> s; // 输入苹果数和剩余力气
    int a, b; // a为椅子高度，b为陶陶手伸直的最大长度
    cin >> a >> b; // 输入椅子高度和手伸直的最大长度
    for (int i = 0; i < n; i++) { // 循环输入每个苹果的高度和需要的力气
        cin >> t[i].x >> t[i].y;
    }
    sort(t, t + n, cmp); // 对苹果数组进行排序，优先按力气升序，其次按高度升序
    int cnt = 0; // 初始化摘到的苹果数为0
    for (int i = 0; i < n; i++) { // 遍历排序后的苹果数组
        if (t[i].x <= b + a && s >= t[i].y) { // 如果苹果能够到且力气足够
            cnt++; // 摘到苹果数加1
            s -= t[i].y; // 扣除摘苹果需要的力气
        }
    }
    cout << cnt << "\n"; // 输出最多能摘到的苹果数
    return 0; // 程序结束
}