《City Horizon》是一道经典的计算机编程题目，来源于北京大学在线评测系统（POJ，Problem Online Judge），题目编号为3277。这道题目属于计算几何的范畴，主要考察的是线段树或者扫描线的应用。
题目描述
在一个二维平面上，有若干个矩形建筑物，每个建筑物都有固定的底边和高度。你需要计算出从某个角度（通常是水平向右）看过去，能够看到的最多的建筑物数量。
输入描述
- 第一行一个整数 ( n )，表示建筑物的数量。
- 接下来的 ( n ) 行，每行两个整数 ( x ) 和 ( h )，分别表示建筑物的底边位置和高度。
输出描述
- 输出一个整数，表示从水平向右看过去，能够看到的最多的建筑物数量。
解题思路
- 离散化：由于建筑物的底边位置可能非常分散，为了方便处理，可以将底边位置进行离散化处理。
- 扫描线：从左到右扫描每个建筑物，维护一个当前能看到的最高的建筑物的高度。
- 线段树：使用线段树来高效地查询和更新当前区间内的最大高度，从而判断当前建筑物是否可见。
具体步骤
- 读取输入：读取建筑物的数量和每个建筑物的底边位置及高度。
- 离散化处理：将所有建筑物的底边位置进行排序，并重新编号。
- 构建线段树：初始化线段树，用于存储和查询每个区间的最大高度。
- 扫描线处理：
- 从左到右遍历每个建筑物。
- 使用线段树查询当前建筑物所在区间的最大高度。
- 如果当前建筑物的高度大于查询到的最大高度，则该建筑物可见，更新线段树。
- 输出结果：统计可见建筑物的数量并输出。
代码示例（伪代码）
#include
using namespace std;
struct Building { int x, h; };
vector
// 线段树相关操作 void update(int node, int start, int end, int idx, int value) { if (start == end) { tree[node] = max(tree[node], value); return; } int mid = (start + end) / 2; if (idx <= mid) update(2 node, start, mid, idx, value); else update(2 node + 1, mid + 1, end, idx, value); tree[node] = max(tree[2 node], tree[2 node + 1]); }
int query(int node, int start, int end, int l, int r) { if (r < start || end < l) return 0; if (l <= start && end <= r) return tree[node]; int mid = (start + end) / 2; return max(query(2 node, start, mid, l, r), query(2 node + 1, mid + 1, end, l, r)); }
int main() { int n; cin >> n; buildings.resize(n); for (int i = 0; i < n; i++) { cin >> buildings[i].x >> buildings[i].h; discretization.push_back(buildings[i].x); }
sort(discretization.begin(), discretization.end());
discretization.erase(unique(discretization.begin(), discretization.end()), discretization.end());
for (auto &b : buildings) {
b.x = lower_bound(discretization.begin(), discretization.end(), b.x) - discretization.begin();
}
int ans = 0;
for (auto &b : buildings) {
int max_h = query(1, 0, discretization.size() - 1, 0, b.x);
if (b.h > max_h) {
ans++;
update(1, 0, discretization.size() - 1, b.x, b.h);
}
}
cout << ans << endl;
return 0;}
注意事项
- 离散化：确保建筑物的底边位置在处理过程中不会丢失。
- 线段树：正确构建和更新线段树，避免边界错误。
- 效率：线段树的操作复杂度为 ( O(\log n) )，整体算法复杂度为 ( O(n \log n) )。
通过以上步骤和代码示例，你应该能够理解和解决这道题目。如果有任何细节不清楚，可以进一步提问。
发表回复