Loading...

洛谷P4995 跳跳!

check评论:0 条 remove_red_eye浏览量:356 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-11-04

贪心裸题

我们直接将高度排序后,先最大,再最小,再次大,再次小......这样轮换跳就可以了,证明的话,完全平方公式展开下就好了

#include <bits/stdc++.h>
using namespace std;
int h[3000],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
    }
    long long int ans=0,now=0;
    sort(h+1,h+n+1);
    for(int i=1;i<=n;i++)
    {
        if(i%2==1)
        {
            ans+=(h[n-(i>>1)]-now)*(h[n-(i>>1)]-now);
            now=h[n-(i>>1)];
        }
        else
        {
            ans+=(h[(i>>1)]-now)*(h[(i>>1)]-now);
            now=h[(i>>1)];
        }
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名