求关注,求赞,求评论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