AcWing 1353. 滑雪场设计(贪心+枚举)

AcWing 1353. 滑雪场设计(贪心+枚举)

思路：最优解的所有山峰高度一定在一个长度为17的区间内，枚举所有可能为最优解的区间，每个区间都用贪心算出最少花费。

#include<bits/stdc++.h>
using namespace std;int arr[1010];int main(){int n;cin>>n;for(int i=1;i<=n;i++)	cin>>arr[i];int res=0x3f3f3f3f;for(int i=0;i<=83;i++){int sum=0;for(int j=1;j<=n;j++){if(arr[j]<i){sum=sum+abs(i-arr[j])*abs(i-arr[j]);}else if(arr[j]>i+17){sum=sum+abs(i+17-arr[j])*abs(i+17-arr[j]);}}res=min(res,sum);}cout<<res;return 0;
}