[链接说明]https://www.acwing.com/problem/content/1355/
样例解释
最佳方案为,将高度为 1 的山峰,增加 3 个单位高度,将高度为 24 的山峰,减少 3 个单位高度。
穷举算法
数据量为 1 ~ 1000,所以可以穷举每一种情况。找出最佳方案。
用 l 表示整改后最低的高度范围,则 l 的范围为 0 ~ 100-17。
遍历 l 为标准的各个情况,即a[i]必须达到l位置;
算出每种情况的花费,花费最小的即为答案。
// 1353._滑雪场设计.cpp #include <iostream> #include<vector> #include<cstdio> #include <algorithm> #include<cstring> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f //以上是模板 const int N = 1010; int a[N] = { 0 }; int min_money = 1e8; //100*100*1000=1e7; int main() { int n; int i; cin >> n; for (i = 0; i < n; i++) { cin >> a[i]; } int l = 0; for (l = 0; l <= 100 - 17; l++) //在整改后的最低高度范围 l 为标准——>确认 a[i] { int money = 0; for (i = 0; i < n; i++) { if (a[i] < l) money += (a[i] - l) * (a[i] - l); if (a[i] > l + 17) //尽量满足max-min=17的情况,此时为最佳方案 money += (a[i] - l - 17) * (a[i] - l - 17); } if (money < min_money) min_money = money; } cout << min_money << endl; return 0; }
之前的错误方法
排队首位相减找大于17的两数——》该法没有注意到中间数-已更改的首位数的值仍>17 且并未修正的情况;
所以对于某些样例出现答案偏小的情况,就WA了