枚举法
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N = 1010;
int n;
int h[N];
auto main() -> int
{
cin >> n;
for(int i = 0; i < n; ++i) cin >> h[i];
int sum = 1e+9;
for(int i = 0; i + 17 <= 100; ++i)
{
int l = i, r = i + 17, a = 0;
for(int j = 0; j < n; ++j)
{
if(h[j] < l) a += (l - h[j]) * (l - h[j]);
if(h[j] > r) a += (h[j] - r) * (h[j] - r);
}
sum = min(a,sum);
}
cout << sum << endl;
return 0;
}
代码思路
1.一开始看到题目觉得简单,然后想的是错误的思路,想着找到最低和最高,保证这两个不会相差17就好,但这种调整只会让最小的变成另外的山。
2.正确的思路: 由于要保证的是最低的最高的相差不大于17, 故最优解的情况一定是所有山峰的高度都在 某个[x , x+17] 区间,由于是每次操作只能操作整数,故区间的只有[0,17], [1,18],....[83,100], 总共有84个区间,故可以穷举,列举这84个区间的情况下,将所有山的高度调整到这个区间内的花费,然后比较这84个区间那种花费最少,即为最优解.这里在每个区间比较的时候,如果高度位于区间内则不用调整,若位于区间左边,将其高度增加到区间左端点,若在区间右边则将其减少到右端点。注意这里通过反证法可以证明区间不可能存在 小于0 和 大于100的最优解, 因为一旦有小于0的高度,这时将它们的高度都移动到0这个点看,由于初始一定是在0 ~ 100区间,这样的代价绝对比移动的小于0的地方代价小,同理不可能在大于100的区间