[Usaco2014 Jan]Ski Course Design
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
农夫John(以后简称“FJ”)的农场里有N(1 <= N <= 1,000)座小山,每座山都有一个在0 .. 100范围内的整数海
拔高度。每年冬天,这些小山上充满积雪时,FJ都会开设一个滑雪训练营。不幸的是,FJ刚刚得知明年用作滑雪训
练营的农场将会被收取一项新税。在仔细地阅读了相关的法律条文后,他发现滑雪营地的官方定义中要求最高和最
低的山丘高度差严格大于17。所以,如果FJ降低他最高小山的高度并升高矮小的小山,使之最高和最低小山的高度
差不超过17,他就能够避免交税。如果改变一座山的高度x个单位需要花费x^2个单位的金钱,FJ最少需要花费多少
钱来改造小山的高度?FJ只会将每座小山改变整数个单位的高度。
输入格式
第1行:整数N。
第2..1+N行:每行包含一座小山的海拔高度。
输出格式
第1行:FJ改造小山高度使它们的最高和最低海拔高度之差至多17个单位所需要花费的最少金钱。
样例
5
1
4
20
21
24
【输入说明】
FJ的农场里有5座小山,海拔高度分别为1, 4, 20, 21和24。
18
【输出说明】
FJ不改变高度为4,20和21的小山的高度。他增加高度为1的小山的高度到4(花费=3^2 = 9)。他降低高度为24的小
山的高度到21,也花费3^2 = 9。