AcWing每日一题--滑雪场设计

https://www.acwing.com/problem/content/1355/

性质：最优方案的所有山峰高度一定在[0 , 100]区间内。

所以可以直接枚举最终区间，计算花费，取最小花费即可。

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1010,INF=0x3f3f3f3f;
 4 int a[N];
 5 int main(void){
 6     int n;
 7     cin>>n;
 8     for(int i=0;i<n;i++){
 9         cin>>a[i];
10     }
11     int res=INF;
12     for(int i=0;i+17<=100;i++){
13         int l=i,r=i+17;
14         int t=0;
15         for(int j=0;j<n;j++){
16             if(a[j]<l) t+=(l-a[j])*(l-a[j]);
17             if(a[j]>r) t+=(a[j]-r)*(a[j]-r);
18         }
19         res=min(res,t);
20     }
21     cout<<res;
22     return 0;
23 }