acwing1353滑雪场设计

acwing1353滑雪场设计

通读题目，找出一些性质：
1.正确区间一定在0~100之间，证明过程如下
反证法：假设存在正确区间端点不在范围内，由于区间点变换前所有点都在[0, 100], 那么我可以将范围外的点移动到端点0处，由于先前的点都在范围内，因此移动的步数肯定更少，那么这个区间就不是代价最少的，和题设矛盾。

2.确定了区间，我们就可以直接枚举长度为17的区间。

#include<algorithm>
#include<iostream>using namespace std;const int N = 1010;
int n, a[N];int main(){cin >> n;for(int i = 0; i < n; i++) cin >> a[i];sort(a, a + n);int res = 1e9;for(int l = 0; l + 17 <= 100; l++) {int cost = 0;int r = l + 17;for(int i = 0; i < n;i ++){if(a[i] < l || a[i] > r){int left = abs(a[i] - l), right = abs(a[i] - r);cost += right > left ? left * left : right * right;}}res = min(res, cost);}cout << res << endl;return 0;
}