洛谷P4995【跳跳】

这个是洛谷月赛的题呢~

我在打月赛的时候写出的代码，但因为没开long long只得了50分QAQ（不开long long见祖宗）

这道题我是拿STL堆做的，题目说是每次的体力值最大，而体力值是(hi−hj)^2，也就是说如果我们在最小的石头上我们就应该往目前最大的石头蹦，如果在最大的石头上就应该往最小的石头上蹦

所以可以开一个大根堆和小根堆维护最大数和最小数，在判断目前是在大石头还是在小石头上，再进行体力值的处理就行了

关于判断位置的方法，我投机取巧地判断了这次跳的次数是奇数还是偶数来判断是在大石头还是小石头上

看代码：

#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
priority_queue<int>p;//大根堆
priority_queue<int,vector<int>,greater<int> >f;//小根堆
int n;
long long ans;//必须开long long！！！我就是这个比赛才得了50！！！
int tmp1,tmp2;
int a[301];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){//读入大小根堆
        scanf("%d",&a[i]);
        p.push(a[i]);
        f.push(a[i]);
    }
    ans+=pow(p.top(),2);//从地面跳到最大的石头
    for(int i=1;i<=n;i++){//交替相减
        if(i%2!=0){//从大石头跳到小石头
            tmp1=p.top();
            p.pop();
            tmp2=f.top();
        }
        if(i%2==0){//从小石头跳到大石头
            tmp1=p.top();
            tmp2=f.top();
            f.pop();
        }
        ans+=pow(tmp1-tmp2,2);
    }
    printf("%lld",ans);
    return 0; 
}