P1478 陶陶摘苹果（升级版）

admin

https://www.luogu.org/problemnew/show/P1478

题目描述
又是一年秋季时，陶陶家的苹果树结了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：
8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2
输出样例#1：
4
说明
所有数据：n<=5000 a<=50 b<=200 s<=1000

      xi<=280  yi<=100

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int i,s,n,a,b,ans;
   
5. struct apple
   
6. {
   
7.     int h,f;
   
8. }k[6000];
   
9. bool cmp(apple x,apple y)
   
10. {
    
11.     return x.f<y.f;
    
12. }
    
13. int main()
    
14. {
    
15.     cin>>n>>s;
    
16.     cin>>a>>b;
    
17.     a=a+b;
    
18.     for(i=1;i<=n;i++)
    
19.         cin>>k[i].h>>k[i].f;
    
20.     sort(k+1,k+n+1,cmp);
    
21.     for(i=1;i<=n;i++)
    
22.         if(a>=k[i].h)
    
23.         {
    
24.             s-=k[i].f;
    
25.             if(s<0)break;
    
26.             ans++;
    
27.         }
    
28.     cout<<ans;
    
29. }
    

复制代码

universehyf

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,s,a,b,c=0;
   
5. int i;
   
6. struct apple{
   
7.     int x;int y;
   
8. }cc[6000];
   
9. bool px(apple c1,apple c2){return c1.y<c2.y;}
   
10. int main()
    
11. {
    
12.     cin>>n>>s>>a>>b;
    
13.     for(i=0;i<=n;i++) cin>>cc[i].x>>cc[i].y;
    
14.     sort(cc,cc+n,px);
    
15.     i=0;
    
16.     while(s>=0)
    
17.     {
    
18.         if(a+b>=cc[i].x)
    
19.         {
    
20.             s=s-cc[i].y;
    
21.             c++;
    
22.         }
    
23.         i++;
    
24.         if(i>=n) break;
    
25.     }
    
26.     cout<<c-1;
    
27.     return 0;
    
28. }

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,w,t1,t,all=0;
    
14. struct node
    
15. {
    
16.         int h,q;
    
17. }a[6000];
    
18. bool cmp(node x,node y)
    
19. {
    
20.         return x.q<y.q;
    
21. }
    
22. int main()
    
23. {
    
24.         scanf("%d%d",&n,&w);
    
25.         scanf("%d%d",&t1,&t);t+=t1;
    
26.         for(int i=1;i<=n;i++)
    
27.                 scanf("%d%d",&a[i].h,&a[i].q);
    
28.         sort(a+1,a+1+n,cmp);
    
29.         for(int i=1;i<=n;i++)
    
30.         {
    
31.                 if(t>=a[i].h)
    
32.                 {
    
33.                         if(w-a[i].q>=0)
    
34.                                 w-=a[i].q,all++;
    
35.                         else
    
36.                         {
    
37.                                 printf("%d",all);
    
38.                                 return 0;
    
39.                         }
    
40.                 }
    
41.         }
    
42.         printf("%d",all);
    
43.         return 0;
    
44. }

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int a,b,s,n,t=1,tot,ans;
   
5. struct apple
   
6. {
   
7.     int h,w;
   
8. }ap[5001];
   
9. bool operator< (apple a,apple b)
   
10. {
    
11.     return a.w<b.w;
    
12. }
    
13. int main()
    
14. {
    
15.     cin>>n>>s;
    
16.     cin>>a>>b;
    
17.     tot=a+b;
    
18.     for(int i=1;i<=n;i++)cin>>ap[i].h>>ap[i].w;
    
19.     sort(ap+1,ap+n+1);
    
20.     while(t<=n)
    
21.     {
    
22.         if(ap[t].w<=s)
    
23.             if(ap[t].h<=tot)ans++,s-=ap[t].w;
    
24.         t++;
    
25.     }
    
26.     cout<<ans;
    
27.     return 0;
    
28. }
    

复制代码