「LGOJ」跳跳!

题意

这一天,你和朋友小 F 一起出去玩耍的时候,遇到了一堆高矮不同的石头

其中第$i$块的石头高度为$h_i$,地面的高度是$h_0=0$

你估计着,从第i块石头跳到第j块石头上耗费的体力值为$(h_i-h_j)^2$

从地面跳到第块石头耗费的体力值是$(h_i)^2$

你决定跳到每个石头上各一次,并最终停在任意一块石头上,并且小跳蛙想耗费尽可能多的体力值

题解

按从小到大排序,h[1]和h[n]分别为当前最大和最小,假设不由最大跳到最小由h[n]跳到h[s],由h[t]跳到h[1],那么欲说明h[n]跳到h[1]才是最大,只需先固定其他跳法,然后证明从n到1比从n到s的方法消耗大
$$
(h[n]-h[1])^2+(h[t]-h[s])^2>(h[n]-h[s])^2+(h[t]-h[1])^2
$$
等价于

$$
-2*h[n]h[1]-2h[t]h[s]>-2h[n]h[s]-2h[t]*h[1]
$$

移项后等价于

$$
$h[n]*h[s]-h[n]*h[1]+h[t]*h[1]-h[t]*h[s]>0
$$

等价于

$$
(h[n]-h[t])*(h[s]-h[1])>0
$$

因为$h[n]>h[t],h[s]>h[1]$

所以原式成立,即
$$
(h[n]-h[1])^2+(h[t]-h[s])^2>(h[n]-h[s])^2+(h[t]-h[1])^2
$$

所以将h[n]和h[1]放一起比可以使结果更大,于是就将它们放一起啦

然后以此类推便有了贪心,先跳最大,再跳最小,然后最大出列,再跳剩下最大的,最小出列……

每一次循环,完成从第i个石头到第n-i个石头,再从n-i个石头到第i个石头,把消耗的体力值加入ans即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

#define RE register

int n,f[350];
long long ans=0;

inline void fread(int &x){
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}

int main(){
fread(n);
for(RE int i=1;i<=n;i++){
fread(f[i]);
}
sort(f+1,f+1+n);
f[0]=0;
for(RE int i=0;i<=(n-1)/2;i++){
ans+=(f[n-i]-f[i])*(f[n-i]-f[i])+(f[n-i]-f[i+1])*(f[n-i]-f[i+1]);
}
printf("%lld",ans);
return 0;
}

0%