Part2.5 P4995 跳跳！ 【贪心】

原题链接：P4995 跳跳！ - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：从第 i 块石头跳到第 j 块石头上耗费的体力值为 (hi - hj)²，从地面跳到第 i 块石头耗费的体力值是  (hi) ²  要求耗费尽可能多的体力值。

思路：从最高跳到最低然后跳到第二高再跳到第二低如此反复

评价：贪心

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 ll d[100005]={0};
 5 bool cmp(ll a,ll b)
 6 {
 7     return a>b;
 8 }
 9 int main()
10 {
11     ll n,ans=0;
12     scanf("%lld",&n);
13     for(int i=0;i)
14         scanf("%lld",&d[i]);
15     sort(d,d+n,cmp);
16     for(int i=0;i2;i++)
17     {
18         ans+=(d[i]-d[n-i])*(d[i]-d[n-i])+(d[i]-d[n-i-1])*(d[i]-d[n-i-1]);
19     }
20     if(n%2==0) printf("%lld",ans);
21     else printf("%lld",ans+(d[n/2]-d[n/2+1])*(d[n/2]-d[n/2+1]));
22     return 0;
23 }