首页 > 代码库 > 【USACO 1.3】Ski Course Design

【USACO 1.3】Ski Course Design

n个点(n<=1000)大小范围[0,100],改变一些点的值,使得极差不超过17,代价为改变值的平方。

枚举修改后的最低高度low,维护最小代价。

/*TASK: skidesignLANG: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 1005using 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);}

  

【USACO 1.3】Ski Course Design