#题解#洛谷 P1904 天际线#离散化#

P1904 天际线 - 洛谷

分析

1. 类似染色问题，P1496 火烧赤壁 - 洛谷

2. 用x数组将所有点的横坐标离散化，用book[i]记录 [ x [ i ] ~ x [ i + 1 ] ) 的高度，（左闭右开）

3. 每次“染色”将高度更新为最大值

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int l[N], r[N], h[N], x[N], book[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int i = 1;int len = 1;while (cin >> l[i] >> h[i] >> r[i]){x[len++] = l[i];x[len++] = r[i];i++;}
//	cout << len << "\n";sort(x + 1, x + len);len = unique(x + 1, x + len) - x - 1;
//	for(int i=1;i<=len;i++)
//		cout<<x[i]<<" ";
//	cout<<"\n";for (int j = 1; j < i; j++){int st = lower_bound (x + 1, x + len+1, l[j]) - x;int ed = lower_bound (x + 1, x + len+1, r[j]) - x;for (int k = st; k < ed; k++)if (book[k] < h[j])book[k] = h[j];}for (int j = 1; j <=len; j++){if (book[j] != book[j - 1]){cout << x[j] << " ";cout << book[j] << " ";}}return 0;
}

Trick/错误总结

1. lower_bound和upper_bound

2. unique不自动排序