题解P1478 -陶陶摘苹果(升级版)

本蒟蒻+菜鸡第二次发题解(第一次没通过XD)

代码如下(代码里面有详细解释)

#include <bits/stdc++.h>//万能头文件
using namespace std;//不加CE
int n,s,a,b,abl,ans;
//以上变量分别表示苹果数量,剩下的力气,椅子的高度,手能伸长的最长高度,陶陶最终能够着的最大高度以及最终答案
struct Apple
{
    int hei,us;
}app[5007];//对于每一个苹果,都有它的两个属性:高度和所需力气,因此可以通过结构体来储存一个苹果
inline bool cmp(Apple a,Apple b)
{
    return a.us < b.us;
}
//由于之后要使用sort快速排序一个结构体变量,但是系统并不知道我们要对这个结构体的哪一个变量进行排序,因此我们需要写一个cmp函数来告诉系统我们需要对结构体的哪一个变量排序
//这里是排序每个苹果所需力气,从小到大排序
int main()
{
    scanf("%d%d%d%d",&n,&s,&a,&b);
    //读入4个变量,如题目
    abl = a + b;//更新abl的值为凳子高度加上陶陶手的长度(也就是陶陶能够着的最高高度)
    for(int i = 1;i <= n;i++)
    {
        scanf("%d%d",&app[i].hei,&app[i].us);
        //读入每个苹果的高度和每个苹果所需力气
    }
    sort(app + 1,app + n + 1,cmp);//调用系统快速排序函数(包含在algorithm头文件里面)一定要记得加刚刚写的cmp比较函数呀,不然会报错的qwq
    //这里是本题的解题关键:贪心,也就是每次都去找所需力气最小的苹果并且能够摘到的去摘,这样就能摘到最多的苹果
    for(int i = 1;i <= n;i++)//遍历每个苹果(此时每个苹果已经按照力气排过序了,因此i越小,所需力气就越小)
    {
        if(app[i].hei <= abl && s >= app[i].us)//如果苹果合法(陶陶够得着并且当前剩余力气足够摘下这个苹果)
        {
            ans++;//把最后答案+1
            s-=app[i].us;//当前剩余力气减少
        }
    }
    printf("%d\n",ans);//输出最终结果
    return 0;//好习惯
}

最后感谢阅读啦qwq (虽然没交上题解去XD)


发表于 2019-08-21 19:40:12 in 题解