#UVa:105-The Skyline Problem

灆洢 2012-03-28 17:13:33

這題就使用陣列儲存該位置的最高點即可,但是要注意左邊界及右邊界的狀況。

還有一個要注意的地方就是:無論建築物最左邊是蓋到哪裡,你都得從1開始輸出。

C++(0.020)

/*******************************************************/
/* UVa 105 The Skyline Problem                         */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/03/28                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  int skyline[10005] = {0};
  int L, H, R;
  int rightest = 0;
  bool space = false;

  while( scanf( "%d%d%d", &L, &H, &R ) != EOF ){
    for( int i = L ; i < R ; i++ )
      if( H > skyline[i] ) skyline[i] = H;
    if( R > rightest ) rightest = R;
  }

  for( int i = 1 ; i <= rightest ; i++ )
    if( skyline[i-1] != skyline[i] ){
      if( space ) printf( " " );
      space = true;
      printf( "%d %d", i, skyline[i] );
    }

  printf( "\n" );

  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料