[链接说明]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了



京公网安备 11010502036488号