题解：[ABC385F] Visible Buildings

看起来很难，实际上是一道简单的~~初中数学题~~。学过一次函数（雾）的都应该会做。

注意点：初二（好像是）学的一次函数

y = kx + b

的

k

其实就是斜率，只是在初中老师一般没有指明

k

是斜率，

b

是

y

轴上的截距而已。

赛时分析（有改动）

题目告诉我们，一个位置

(X_i, H_i)

的建筑从

(0, h)

可见，当且仅当从

(0, h)

到建筑

i

的视线不会被其他建筑阻挡。

不妨用数学语言表达：建筑

i

可见的条件是，从

(0, h)

到

(X_i, H_i)

的斜率大于从

(0, h)

到所有前面建筑的斜率。

学过一次函数的都知道，

(0, h)

到

(X_i, H_i)

的斜率公式为：

\text{slope}_i = \frac{H_i - h}{X_i}

我们说建筑

i

是可见的，当且仅当：

\frac{H_i - h}{X_i} > \max_{j < i} \left( \frac{H_j - h}{X_j} \right)

也就是说：

h > \frac{H_j X_i - H_i X_j}{X_i - X_j}

对于所有

j < i

都需要满足。

因此，为了使所有建筑物可见，

h

必须大于上述公式中最大值。不难发现，

h

的最大值是由两个相邻的建筑

(i-1, i)

决定的。因此只需考虑相邻建筑即可，将时间复杂度优化为

O(N)

。

我们来模拟一下第一个样例。

i = 2

时，

h_{2} = \frac{2 \times 5 - 4 \times 3}{5 - 3} = \frac{10 - 12}{2} = -1

。

i = 3

时，

h_{3} = \frac{4 \times 7 - 5 \times 5}{7 - 5} = \frac{28 - 25}{2} = 1.5

所以，最大值

min\{h_i\} = 1.5

。

赛时代码

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
double maxh = - 1e18;
pair <int, int> h[200010];
signed main() {
	ios :: sync_with_stdio(false);
	cin . tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> h[i] . first >> h[i] . second; // 输入
	for (int i = 2; i <= n; i ++) {
		// 注意需要从第二个开始，因为取的是相邻的
		int X_1 = h[i] . first, H_1 = h[i] . second; 
		int X_2 = h[i - 1] . first, H_2 = h[i - 1] . second;
		// 这里分别表示出相邻的两栋楼
		maxh = max(maxh, (double)(H_2 * X_1 - H_1 * X_2) / (double)(X_1 - X_2));
		// 求斜率并取最大值
	}
	if (maxh < 0) cout << "-1" << endl;
	// 无解
	else cout << fixed << setprecision(12) << maxh << endl;
	// 输出结果
	return 0;
}

~~完结撒花，记得点赞 [嘿嘿]。~~

题解：[ABC385F] Visible Buildings

文章操作

赛时分析（有改动）

赛时代码

相关推荐

评论

题解：[ABC385F] Visible Buildings