题解 P4995 【跳跳!】

· · 题解

数竞党一眼贪心,所以给出以下证明。

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

等价于 $-2*h[n]*h[1]-2*h[t]*h[s]>-2*h[n]*h[s]-2*h[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]放一起比可以使结果更大,于是就将它们放一起啦,然后以此类推便有了贪心,先跳最大,再跳最小,然后最大出列,再跳剩下最大的,最小出列…… 下面p党代码 ```pascal var h:array[1..300] of longint; //高度 a:array[1..10000] of longint; j,i,x,n:longint; k:boolean; //记录是最大出列还是最小出列 ans:int64; begin readln(n); for i:=1 to n do begin read(x); inc(a[x]); end; j:=0; for i:=1 to 10000 do if a[i]=1 then begin inc(j); h[j]:=i; end; //计数排序 i:=1; k:=true; //一开始跳到了最大,此时循环是最大出列,k=true时最大出列 ans:=h[j]*h[j]; while i<>j do //只要还没只剩一根石头就继续跳 begin inc(ans,(h[j]-h[i])*(h[j]-h[i])); //ans增加 if k then dec(j) //由最大到最小,最大出列 else inc(i); //由最小到最大,最小出列 k:=not k; //每次跳都是另一个出列了 end; writeln(ans); end. ``` 最后祝在座各位noip rp++(蒟蒻即将退赛搞数学惹)