n个点(n<=1000)大小范围[0,100],改变一些点的值,使得极差不超过17,代价为改变值的平方。
枚举修改后的最低高度low,维护最小代价。
/*
TASK: skidesign
LANG:C++
URL:http://train.usaco.org/usacoprob2?a=LxVrSLLAzuR&S=skidesign
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
#define N 1005
using namespace std;
int n,h[N];
int tol=0x3f3f3f3f;
int sqr(int x){
return x*x;
}
int main() {
freopen("skidesign.in","r",stdin);
freopen("skidesign.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&h[i]);
}
sort(h+1,h+1+n);
for(int low=h[1];low<=h[n]-17;low++){
int ans=0;
for(int i=1;i<=n;i++){
if(h[i]<low)ans+=sqr(low-h[i]);
else if(h[i]>low+17)ans+=sqr(h[i]-low-17);
}
tol=min(tol,ans);
}
printf("%d\n",tol);
}