题解 P3650 【[USACO1.3]滑雪课程设计Ski Course Design】

xfydemx · 2017-10-03 08:28:36 · 题解

这题思路很清晰，暴力出奇迹

我就再说一下枚举的细节吧：

-找出上下界限

-以界限为界判断高低，若高于则全部削去，低于则削去差大于17的部分

上代码：

#include<bits/stdc++.h>
using namespace  std;
int a[100000],n,minn,s=1e9+1,sum;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+n+1);//找出最大和最小情况，这里用sort只是我强行偷懒
    for(int j=a[1];j<=a[n];j++)
    {
        sum=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]-j>17) sum+=(a[i]-j-17)*(a[i]-j-17);   //若高于则全部削去，低于则削去差大于17的部分
            if(a[i]<j) sum+=(a[i]-j)*(a[i]-j);
        }    
        s=min(sum,s);  //维护结果
    }
    cout<<s;
}