题解 P1478 【陶陶摘苹果（升级版）】
【睿智萌新第一次写题解却因为重复原因审核都没过】
【留在这当黑历史丢人吧】
本辣鸡第一次发表题解大家就当看着玩吧qwq
.
（入门难度升级了还是很好写2333）
.
下面为奇妙の题解
.
看着上面的一群dalao都写的很详细了我就糊点奇怪的东西在这吧
.
首先是解题思路，这道题相对于之前那道入门难度的题目新加入了力气这个变量，要在剩余力气的范围内尽量摘到最多的苹果，首先想到的就是贪心吧。
（不知道有没有萌新不知道贪心算法是啥呢，那我顺便说一下吧，个人觉得这是最容易理解的算法，毕竟和生活实际很接近，比如说你有十块钱，有两个地方卖苹果，苹果的质量都是一模一样的，但家店卖三元一个，另一家卖五元一个，如果你想多吃几个苹果的话，当然会选择去价格便宜的那家店）
这题也是一样，要使得到的苹果最多，当然要每次都摘那个最省力的苹果，这样最后的结果一定是最优的
（再提一句，贪心并不能适用于所有的情况，如果前面的选择会影响后面的情况，那么贪心就不适用了，详情可见数字三角形（P1216） 。）
（PS：如果还是理解不了的话我再举个例子，比如说刚刚的买苹果，如果你一直买三块钱的苹果，导致卖五块钱的那家店破了产，然后三块钱的店趁机垄断市场把三块钱提高到十块钱，这时候你想吃苹果就只能以亏爆的价格购买，这种情况下两个店都买一些或者均衡着买才是最终的最佳情况）
好了，如果知道贪心算法是什么样的这题就很简单了。
说实话我第一眼看见这个题脑子里想到的直接是 贪心+sort+前缀和 一遍过（前缀和其实可以不用，直接一遍循环过来用时可能更少）
考虑到萌新可能不懂sort和前缀和，所以我还是慢慢讲吧（疯狂拖长度）
首先，使用贪心需要找到每次的最小值，这时候使用排序肯定是最优且最方便的
但是如果不会排序呢？放心，这个题不用排序直接暴力也能过
下面贴代码
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 5005
#define MAX 999999999
//新人注意，这里的define语句是很有用的哦
//可以避免对大数字的重复输入
int n,high[MAXN],tired[MAXN],s,a,b,num;
//n为苹果的个数
//high为各苹果高度
//tired 为摘苹果需要的体力
//s,a,b为剩余体力，凳子高，伸手高度
//num为能摘到的果子数
int main(){
cin>>n>>s>>a>>b;
//输入
a+=b;
//注意这里，a，b在此题中不单独起作用，判定时是作为整体，所以可直接将b加到a上
for(int i=1;i<=n;i++){//输入各果子数据
scanf("%d%d",high+i,tired+i);
}
int min=MAX,minn;
//每次找耗体力最少的苹果
//minn用来记录找到的苹果的标号
for(int i=1;i<=n;i++){
min=MAX;minn=0;
//查找之前先归零
for(int j=1;j<=n;j++){
if(high[j]<=a&&tired[j]<min){
min=tired[j];minn=j;
}
//依次查找，找到比min小的就更新min和minn
}
if(s>=min){//把这几个MAX换为999999999后你就知道之前的define语句有什么作用了qwq
s-=min;num++;tired[minn]=MAX;
}else break;
//如果可以摘的话，就摘下来并记录它
//(把tired设为最大值后不会再次记录此果子
}
cout<<num<<endl;//正经の输出
return 0;//正经の结束
}
注：这个程序涉及到重复找最小值的操作（各位应该都会吧不会我也懒得讲了qwq
虽然复杂度为O(n^2),但对于本题还是可以AC的（顺带还能练习多次找最小值）
接下来是我自己习惯的做法，直接sort+前缀和
sort的话...反正我已经中毒了，除了sort不会其他的排序了..
(我知道这样不能理解排序的精髓而且最坏情况会退化到O(N^2)但sort真的很好用啊代码又少还能自己带比较函数qwq）
（建议新人先把各个排序都理解清楚了再调用此函数）
PS:使用sort需调用algorithm头文件
前缀和其实也很好理解，就是把本来表示单个果子的疲劳值的数组变成了表示前i各果子的数组
对于本题可能没有什么作用，但是如果给出多个体力值s求最大能摘几个的话就可以大幅度优化复杂度，所以我建议不会使用的OIer把这种方法仔细地理解清楚
(仍然是例子，比如说本来排序后耗费体力值为 3 5 6 7,求前缀和后数组变为 3 8 14 21, 这样，只用比较s与21的大小就知道是否可以摘前四个果子，是不是比依次用s减去 3 5 6 7快很多呢？
AC代码如下
#include<iostream>
#include<algorithm>
using namespace std;
int n,s,a,b;
//分别为个数，体力，凳子高，身高
int i=1,apple[5005];
//i用来记录读入的苹果，apple用来记录各苹果需要的体力
int main(){
cin>>n>>s>>a>>b;//普通の读入
a+=b;//上面讲过了哦
int high,tire;
//读入时使用的变量
while(cin>>high>>tire){
//某奇特的输入技巧，可直接判断是否输入完并输入值
if(high==0)break;
//测试时加入的，否则在控制台程序不知道你是否输入完了（但文件读写就不会出现这种情况）
if(high<=a){
apple[i]=tire;i++;
}
//可以采摘就记录并更改i的值准备记录下一个
}
//这里用到一个技巧，对于过高的苹果，只能看着发呆，
//当前体力值和需要体力值都不能让它下来，所以直接跳过它开始下一个
sort(apple+1,apple+i);
//排序毒品
for(int j=2;j<=i;j++){
apple[j]+=apple[j-1];
}
//计算前缀和（也可以不用
for(int j=1;j<=i;j++){
if(s<apple[j]){
cout<<j-1<<endl;return 0;
}
}//判定s与所有果子的大小
cout<<i-1<<endl;
return 0;
} PS：虽然说不能过分依赖sort，但这种排序方法还是要掌握的，因为
①：头文件自带的函数基本上都是最佳优化的，可以节省很多时间
②：考试时时间是很紧的，花时间手写一个排序算法不如直接写一个sort＋自定义函数
③：sort功能十分强大，不仅可以对任何类型排序，还可以自定义排序的方法，作用极大
（关于sort怎么用我就不多说了，百度上都有很详细的讲解，记住是左闭右开的就行
.
.
~~是不是已经觉得很多了？ 其实我下面还有两种解法哈哈哈哈哈没想到吧~~
.
.
通过刚才的sort排序，我们可以很快地把答案求出来。
但对于这种简单（对于有一定算法基础的人来说）题，不能只满足于把这个题目写出来
大家想一想，使用sort的确一遍过了，但是输出了后，你知道他到底摘了哪几个果子吗？
如果题目让我们输出具体摘到的是哪几个果子，这时候怎么办呢？
使用一开始的非排序算法的确可以，但太慢了不是吗？
如果使用sort，顺序又会乱，无法记录
这时候，就要使用结构体来记录多组数据了
Warning：新人不必急着把下面的两个解法完全理解透，毕竟这样玩已经有超过普及-难度的意思了
（但也可以先看看嘛毕竟文字还是很多的qwq）
代码如下：
注：加入了某些奇♂怪♂的东西
//涛涛摘苹果升级版 使用结构体加sort
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int appnum,a,b,power;
//分别为 苹果数，凳子高，身高，体力
struct apple0{
int length,tired;
int rank;
} apple[5005];
//定义一个结构体，
//length和tired记录高度和疲劳值
//使用rank来记录第几个
bool cmp(apple0 a,apple0 b){
if(a.tired<b.tired)return 1;
return 0;
}
//自定义比较函数， 按照疲劳值升序排列
int main(){
cin>>appnum>>power>>a>>b;//简单の输入
a+=b;//见之前代码
int len,tir;
for(int i=1;i<=appnum;i++){
scanf("%d%d",&len,&tir);
apple[i].length=len;apple[i].tired=tir;apple[i].rank=i;
}
//输入并记录各个数值
sort(apple+1,apple+appnum+1,cmp);
int cnt=0;
cout<<"摘到了哪几个果子呢？"<<endl;
for(int i=1;i<=appnum;i++){
if(power>=apple[i].tired&&a>=apple[i].length){
power-=apple[i].tired;
cnt++;cout<<apple[i].rank<<' ';
}
if(power<apple[i].tired&&a>=apple[i].length)break;//注意：在排序的背景下，这里加不加后半段都无所谓，反正后面的你都摘不到了，是吗？
}
//未使用前缀和，但通过rank的值输出了是哪几个
cout<<endl;
cout<<"涛涛这傻孩子摘到的果子数："<<endl<<cnt;
return 0;
}
好了，说道这里也差不多结束了
其实这个题用桶排也是可以的，因为看见有dalao写过所以我就不多写了
（我会跟你说是因为我写了四个代码后实在懒得再写了吗）
那下面就是我要说的最后一个方法，使用动态规划的思路，用记忆化解01背包的方法写这个题
因为可以把每个苹果的价值看为1，需要空间为疲劳值，所以01背包的方法是完全适用的
（虽然说有杀鸡用牛刀的嫌疑但是用来练习01背包还是可以的~）
直接扔代码吧
//涛涛摘苹果升级版 -- 蛇皮解法：01背包
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int apple[5005];
int n,power;
int i=1;
int ed[5005][1005];
//记忆化使用，保证每个点只算一遍
int maxn;
int dfs(int step,int power){
if(step==i)return ed[step][power]=0;//同记忆化
if(ed[step][power]>=0)return ed[step][power];
if(power>=apple[step])return ed[step][power]=max(dfs(step+1,power-apple[step])+1,dfs(step+1,power));//还能摘就继续搜索
else return ed[step][power]=dfs(step+1,power);
}
int main(){
int a,b;
cin>>n>>power>>a>>b;
a+=b;
int high=0,tir=0;
while(cin>>high>>tir){//读入各个苹果(对于太高的苹果直接忽略就是了)
if(high<=a){
apple[i]=tir;i+=1;
}else continue;
}
memset(ed,-1,sizeof(ed));
cout<<dfs(1,power);//直接输出结果
} 好了，到此四种解法已全部展示完毕
手打不易，如果你觉得这篇题解对你有意义的话，点个赞或者评论支持一下都可以哦~
如果有不足的地方，也欢迎dalao指正，比较我是第一次写题解，而且本咸鱼学算法的时间也不超过两星期，可能错误会比较多呢....qwq
感谢各位~