USACO 1.4.6 滑雪场设计

USACO 1.4.6 滑雪场设计

1.4.6 滑雪场设计

题目考查

暴力枚举 三分

解题思路

我们考虑山的高度范围为 [ 0 , 100 ] [0, 100] [0,100], 因此, 我们一定能找到一个 l ∈ [ 0 , 83 ] , r = l + 17 l in [0, 83], r = l + 17 l∈[0,83],r=l+17, 使得所有山峰高度位于 [ l , r ] [l, r] [l,r]区间时, 花费最小.

因此思路1: 我们可以暴力枚举所有左端点, 然后所有花费取最小值即可

考虑优化思路1, 因为通常题目的值域范围不会那么小, 如果值域变为 [ 0 , 1 0 9 ] [0, 10^9] [0,109], 我们如何去做呢?

我们发现, 如果以左端点 l l l的选取建立 O x Ox Ox, 以花费 c o s t cost cost建立 O y Oy Oy, 那么整体函数图像应该是呈现一个开口向上的二次函数形式. 我们可以通过三分来求解.

因此思路2: 三分区间左端点.

我通常习惯用浮点数三分的方式, 来处理整数三分, 最后判断的时候, 判断一下三分结果左右的一个小区间即可.

题目细节

在进行最后的小区间判断时, 由于我们之前的判断函数返回的是浮点数类型, 而答案是整型. 如果怕有精度问题, 可以重写一个计算函数.

AC代码

暴力枚举

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E3 + 10;
int a[N];
int main()
{int n; cin >> n;rep(i, n) scanf("%d", &a[i]);int res = INT_MAX;for (int h = 0; h <= 83; ++h) {int now = 0;rep(i, n) {if (a[i] >= h and a[i] <= h + 17) continue;int up = h + 17;now += min((a[i] - h) * (a[i] - h), (a[i] - up) * (a[i] - up));}res = min(res, now);}cout << res << endl;return 0;
}

三分

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E3 + 10;
const double eps = 1E-6;
int n;
int a[N];
double fact(double x) {double res = 0;double up = x + 17;rep(i, n) {if (a[i] >= x and a[i] <= up) continue;double qaq = min((a[i] - x) * (a[i] - x), (a[i] - up) * (a[i] - up));res += qaq;}return res;
}
int main()
{cin >> n;rep(i, n) scanf("%d", &a[i]);double l = 0, r = 83;while (r - l > eps) {double mid = (l + r) / 2;double midl = mid - eps, midr = mid + eps;if (fact(midl) < fact(midr)) r = midl;else l = midr;}int res = INT_MAX;for (int i = max<int>(l - 5, 0); i <= l + 5; ++i) {res = min<int>(res, fact(i)); //如果怕有精度问题, 可以再写一个函数计算}cout << res << endl;return 0;
}

END