The topic is as follows
It's autumn again, and Tao Tao's apple tree bears n fruits. Tao Tao ran to pick apples again, this time he had a chair measuring a centimeter. When he can't reach, he will stand on the chair and try again.
This time, the difference from the first question of the popularization group of NOIp2005 is: Tao Tao moved the stool before, and only s strength is left. Of course, every time you pick an apple, you have to use a certain amount of strength. Tao Tao wants to know how many apples can be picked at most before s<0.
It is now known that n apples reach the height of the ground xi, the height of the chair a, the maximum length of the pottery hand stretched b, the remaining strength of the pottery s, the strength required for the pottery to pick an apple, yi, the pottery can be picked at most How many apples.
Input format
Line 1: Two numbers, number of apples, n, strength s.
Line 2: Two numbers The height of the chair a, the maximum length of the Taotao hand stretched b.
Row 3~row 3+n−1: Two numbers per row The height of the apple xi, the strength required to pick this apple yi.
There is only one integer, which represents the maximum number of apples that Tao Tao can pick.
Enter
8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2
Output
4
Problem analysis This is a simulated printing problem. We first rank the least effortlessly first, and then we can use the height to judge, so that we are always picking the least effortlessly, so that we can get the most apples.
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+6; struct node{ int x,y; }s[maxn]; bool cmp(node q,node w) { return q.y<w.y; } int main() { int n,z,a,b; int ans=0; cin>>n>>z>>a>>b; for(int i=1;i<=n;i++) { cin>>s[i].x; cin>>s[i].y; } sort(s+1,s+1+n,cmp); for(int i=1;i<=n&&z>=0;i++) { if(s[i].x<=a+b&&z-s[i].y>=0) { z-=s[i].y; ans++; } } cout<<ans<<endl; }
