程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [POJ]3277.City Horizon

[POJ]3277.City Horizon

編輯:C++入門知識

[POJ]3277.City Horizon


Description

Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.

The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,000) buildings. Building i’s silhouette has a base that spans locations Ai through Bi along the horizon (1 ≤ Ai < Bi ≤ 1,000,000,000) and has height Hi (1 ≤ Hi ≤ 1,000,000,000). Determine the area, in square units, of the aggregate silhouette formed by all N buildings.

Input

Line 1: A single integer: N
Lines 2..N+1: Input line i+1 describes building i with three space-separated integers: Ai, Bi, and Hi

Output

Line 1: The total area, in square units, of the silhouettes formed by all N buildings

Sample Input

4
2 5 1
9 10 4
6 8 2
4 6 3

Sample Output

16

Hint

The first building overlaps with the fourth building for an area of 1 square unit, so the total area is just 3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.

Source

USACO 2007 Open Silver

題目大意

如圖所示,在一條水平線上有N個建築物,建築物都是長方形的,且可以互相遮蓋。給出每個建築物的左右坐標值Ai,Bi以及每個建築物的高Hi,需要計算出這些建築物總共覆蓋的面積。

題目數據范圍:
建築物個數N:1 <= N <= 40000
建築物左右坐標值Ai, Bi:1 <= Ai,Bi <= 10^9
建築物的高度Hi:1 <= Hi <= 10^9

這裡寫圖片描述vczixL/W0NK7uPbM2MritcTM9bz+o6zL+dPQtcS+2NDOtcTSu7Hf1NrSu8z11rHP38nPo6zO0sPHv8nS1LrDusPA+9PD1eK49sz1vP6jutPJ09rL+dPQtcS+2NDO1NrV4sz11rHP38nPtcTNttOwvvnT677Y0M61xNK7uPax37Okz+C1yKGjy/nS1KOsztLDx7/J0tSw0b7Y0M6hsNG5y/WhsbPJPHN0cm9uZz7Wsc/fyc+1xM/fts48L3N0cm9uZz6jrMfSw7/M9c/fts62vNPQ0ru49jxzdHJvbmc+yKjWtTwvc3Ryb25nPqOs1eK49sio1rW+zcrHvtjQzrXEuN+2yEhpoaPEx8O0o6zO0sPHvs2/ydLUwPvTw8/fts7K97340NC0psDto6y8xsvjw+a7/bKivs3P4LWx09q8xsvjtPjIqLXEz9+2zrKio6y8tFMgPSBIICogKEIgqEMgQSmho7WxxLPM9c/fts6xu7bgtM64srjHyrGjqLHIyOfNvNbQtcTP37bOQTJCMaOpo6zWu8ihSNa11+6087XEvfjQ0LzGy+Oho8jnzbwyLjHW0LXEvtjQzsPmu/2yos6qo7pTID0gSDEqKEIxIKhDIEExKSArIEgyICogKEEzIKhDIEIyKSArIEgzICogKEIzIKhDIEEzKSC7+bG+y7zCt8fls/7By6OsztLDx8/W1NrAtL+8wse+38zlyrXP1qGjPC9wPgoKPHA+08nT2szixL/W0L7Y0M61xNfz09LX+LHqtcS3ts6nt8ezo7TzKDEgPD0gQWksQmkgPD0gMTBeOSmjrMjnufu9qMGitPPQoc6qWzEsIDEwXjkptcTP37bOyvfU8rvh1bzTw7Tzwb+1xL/VvOSho87Sw8eyydPD0rvW1jxzdHJvbmc+wOvJoruvPC9zdHJvbmc+tcTLvM/rwLS0psDt1eK49s7KzOKjrNXi1tbLvMK31NrP37bOyve1xMzixL/W0NKyyse+rbOju+HTw7W9tcSho7+8wse1vdK7ubLWu9PQTiA8PSA0MDAwMLj2vtjQzqOsxMfDtKOs1eLQqb7Y0M7Su7my0rLWu9PQMiAqIDQwMDAwID0gODAwMDC49tfz09LX+LHq1rWho87Sw8fK18/IvavV4jgwMDAwuPbX+LHq1rWwtLTz0KHFxdDyo6y21MXF0PK687XE1/ix6tLAtM64s9Po0ru49tDC1/ix6ta1a6OoMSA8PSBrIDw9IDgwMDAwo6mjrNXi0fnO0sPHvs2w0bOktsjOqlsxLCAxMF45KbXEz9+2zsDryaK7r7PJWzEsODAwMDAptcTP37bOwcujrLb41+6687zGy+O94bn7yrGjrNa70OjSqrC01dXQwtf4serWtdXSu9jUrcq81/ix6ta1sqK0+sjrvMbL47y0v8mhozwvcD4KCjxwPr7Z0ru49rzytaW1xMD919OjrLzZyejP1tTa09DI/cz1z9+2zlsyMCw2MCksWzEwLDUwKSxbNSw1NSmho87Sw8e9q9XiyP3M9c/fts61xNfz09K2y7XjvfjQ0MXF0PKjrMbkveG5+86qNSwxMCwyMCw1MCw1NSw2MKGjztLDx72ry/zDx9LAtM64s8nP0MLWtTEsMiwzLDQsNSwgNqGj1eLR+dStyry1xMj9zPXP37bOsbvA68miu6/OqlszLDYpLFsyLDQpLFsxLDUpo6zO0sPHvs2/ydLU1NpbMSw2KbXEv9W85MTattTG5L340NC0psDtwcuho9Xivs3Kx8DryaK7r7XEzf7BpqGjPC9wPgoKPHA+u9i1vdStzsrM4snPwLSjrLWxvtjQzsv5zbbTsLXEz9+2zrG7wOvJoruv0tS686OsztLDx77Nv8nS1L2owaLP37bOyvfBy6Gj0+vWrsewvbK5/bXEs/XKvLuvwtTT0LK7zayjrM/W1NrDv7j2z9+2zsr3tcS92rXjsrvWu8rHvMfCvMbky/m0+rHttcTP37bOyse38bG7uLK4x6OstvjH0tKqvMfCvLG7uLK4x7XEz9+2zrXEyKjWtaGjw7+0zrzTyOvSu7j2vtjQzr7NysfU2s/fts7K98nPsuXI69K7zPW0+MiotcTP37bOo6yy5cjrtcTKtc/Wuf2zzNPr1q7HsLXE0rLT0LK7zayho8jnufu1scewz9+2zs3qyKu4srjHwcu92rXjy/m0+rHttcTP37bOo6zEx8O0sci9z9Xiwb249s/fts61xMio1rW089ChoaPI57n7vdq148v5tPqx7bXEz9+2zrXEyKjWtdChu/LV39Ta1q7HsLj5sb7OtLG7uLK4x6Os1PK9q8bkyKjWtbj80MLOqrWxx7DP37bOtcTIqNa1oaM8L3A+CgoKCjxwcmUgY2xhc3M9"brush:java;">// 插入 void Insert(int left,int right,int height,int num){ // 若插入的線段完全覆蓋當前節點所表示的線段 if(intervalTree[num].left == left && intervalTree[num].right == right){ // 更新權值(高度) if(intervalTree[num].height < height){ intervalTree[num].height = height; }//if intervalTree[num].cover = 1; return; }//if // 當前節點的左子節點所代表的線段包含插入的線段 if(right <= intervalTree[num].mid){ Insert(left,right,height,2*num); }//if // 當前節點的右子節點所代表的線段包含插入的線段 else if(left >= intervalTree[num].mid){ Insert(left,right,height,2*num+1); }//if // 插入的線段跨越了當前節點所代表線段的中點 else{ Insert(left,intervalTree[num].mid,height,2*num); Insert(intervalTree[num].mid,right,height,2*num+1); }//else }

而最後計算面積並時,需要遍歷整個線段樹,因為這樣才能確定每個從根節點到葉節點的路徑上,即每個元線段上(形如[a,a+1)的線段),最大的高度是多少。統計過程從根向葉遍歷,遍歷過程中統計高度的最大值,並在葉節點上進行計算,非葉節點的計算結果是其左右子節點的計算結果之和。實現的代碼如下(因為計算結果的數據超過了int的范圍,所以使用long long 數據類型):

// 計算面積
long long Cal(int h,int num){
    // 統計過程從根向葉遍歷,遍歷過程中統計高度的最大值
    if(h > builds[num].height){
        builds[num].height = h;
    }//if
    // 葉節點上進行計算
    if(builds[num].left + 1 == builds[num].right){
        long long area = builds[num].height *
        (hash[builds[num].right] - hash[builds[num].left]);
        return area;
    }//if
    // 非葉節點的計算結果是其左右子節點的計算結果之和
    return Cal(builds[num].height,2*num) +
    Cal(builds[num].height,2*num+1);
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved