競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 105 - The Skyline Problem

ようやく当日投稿が間に合いました。
ABCが全て終わってしまったのでとりあえずUVaを解いていこうと思います。

- 問題概要

ある町があって、ビルが並んでいます。
ビルのx座標の左端、右端、z座標の高さが与えられ、y軸上の十分に遠いところから町を眺めたときどのように見えるかという問題です。

- 解法

全ての座標は10000以下、ビルの数は5000以下ということなので、
あるビルiの情報(L_i,R_i,H_i)が与えられたとき、ある座標xの高さをH(x)とすると
L_i \le j < R_iについて、H(j)=max(H(j),H_i)という処理をナイーブに行ってやればよいです。
これを全てのiについて行うとき、計算量は最悪10000*5000 < 10^8となるので十分間に合います。
出力する際は座標0から順に配列を参照して高さが変化したときに出力するだけでよいです。
Presentation Errorが出る場合は最後の改行の前に一つ空白を入れてしまっていないか注意してみてください。

この問題はヒープを使うとビルの個数をNとしたときO(N\log N)で実装できます。

- ソースコード

#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>
using namespace std;
#define rep(i,a,b) for(auto (i)=(a);i<(b);(i)++)

int height[10001] = { 0 };

int main(void){
	int L, H, R;
	while (cin >> L>>H>>R){
		//if (L == -1)break;
		rep(i, L, R)
			height[i] = max(height[i], H);
	}
	int prev=0;
	bool flag = false;
	rep(i, 0, 10001){
		if (prev != height[i]){
			if (flag)
				cout << " " ;
			flag = true;
			printf("%d %d", i, prev=height[i]);
		}
	}
	cout << endl;
	return(0);
}