摘苹果问题

抽风了的blog,这篇莫名其妙的就在本地消失了,正好就把题目加上重写一遍。


题目描述

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

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

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

输入格式

第1行:两个数 苹果数n,力气s。

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

第3行~第3+n-1行:每行两个数 苹果高度xi,摘这个苹果需要的力气yi。

输出格式

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


题目对我而言的坑点在于。。

  1. 要先按照花费力气大小排序
  2. 对应的距离也应当排序。。所以用了结构体
  3. sort函数的运用
  4. 数组大小
  5. 如何定义结构体数组(第一次使用结构体写的题,当然要记下来啦~)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct apple
{
int x; //苹果高度
int y; //所需力气
};
bool cmp(const apple &a,const apple &b)
{
return a.y<b.y;
}
int main()
{
int n,s,a,b; //苹果数n,力气s,椅子的高度a,手伸直的最大长度b
int t;
apple a1[6000];
int sum=0;
cin>>n>>s;
cin>>a>>b;
for(int i=0;i<n;i++)
{
cin>>a1[i].x;
cin>>a1[i].y;
}
sort(a1,a1+n,cmp);
for(int i=0;i<n;i++)
{
if(a1[i].x>a+b)
continue;
else
{
s=s-a1[i].y;
// cout<<s<<endl;
if(s<0)
break;
sum++;
}
}
cout<<sum<<endl;
return 0;
}
-------------本文结束感谢您的阅读-------------