洛谷P4995 跳跳！题解

求关注，求赞，求评论QAQ

题目：https://www.luogu.org/problemnew/show/P4995

简单描述一下吧，就是说有n块石头，起始可以跳到任何一块上面，接着也是，只不过每一块石头只能跳一次,求耗费的最大的体力（计算方法见链接）

分析：

这道题一看，我们要最大化我们的体力值，说明我们的每一次要尽可能的跳的远，此时我们就可以采用贪心的思想，把每一次的跳跃体力值最大化，那么就能得到体力值总和的最大化。

先把序列从小到大排序，因为我们知道，每次要跳的尽可能远，所以说我们可以第一步先跳到排序后第n个石头，第二步跳到第1个石头。

不难发现，这样的话就是正解。

代码：

#include<bits/stdc++.h>

using namespace std;

long long m,n,a[1000],ans;

int main()

{

    scanf("%d",&m);

    for(int i=1;i<=m;i++) scanf("%lld",a[i]);

    sort(a+1,a+m+1);//从小到大排序

    int head=1,now=0,flag=0,tail=m;//head记录的是从头开始，tail记录从n开始，flag记录这一步该头还是该尾

    while(head<=tail)//当两个还没有重合之时

    {

        if(!flag)

        {

            ans+=(now-a[tail])*(now-a[tail]);

            now=a[tail];

            tail--;

            flag=1;

        }

        else

        {

            ans+=(now-a[head])*(now-a[head]);

            now=a[head];

            head++;

            flag=0;

        }

        //分两种情况，每次别忘了记录下当前在哪

    }

    printf("%lld\n",ans);

}

求关注，求赞，求评论QAQ