【題目描述】 最近，afy決定給TOJ印刷廣告，廣告牌是刷在城市的建筑物上的，城市里有緊靠著的N個(gè)建筑。afy決定在上面找一塊盡可能大的矩形放置廣告牌。我們假設(shè)每個(gè)建筑物都有一個(gè)高度，從左到右給出每個(gè)建筑物的高度H1,H2…HN，且1<=Hi<=1,000,000,000，并且我們假設(shè)每個(gè)建筑物的寬度均為1。要求輸出廣告牌的最大面積。 【輸入格式】 第一行是一個(gè)數(shù)n (n<= 400,000 ） 第二行是n個(gè)數(shù)，分別表示每個(gè)建筑物高度H1,H2…HN，且1<=Hi<=1,000,000,000。 【輸出格式】 輸出文件 ad.out 中一共有一行，表示廣告牌的最大面積。 【 樣例輸入】 6 5 8 4 4 8 4 【樣例輸出】 24 【分析】 首先可以想到，在廣告覆蓋的樓房中，最矮的樓房（并不是指所有樓房中最矮的那個(gè)）一定被廣告完全覆蓋了。所以可以枚舉最矮的樓房，求出向左、向右分別可以延伸多遠(yuǎn)（即大于等于該樓房），然后打擂臺(tái)即可。 用單調(diào)隊(duì)列預(yù)處理向左、向右分別延伸的距離可以優(yōu)化程序。
#include<iostream>#include<cstdio>using namespace std;#define MAXN 400000#define LL long longint h[400010];int n;int Queue[400010];int L[400010],R[400010];int main(){ cin>>n; int i; for (i=1;i<=n;i++) cin>>h[i]; h[0]=h[n+1]=-1; Queue[0]=0; int Head=0,Tail=1; for (i=1;i<=n;i++) { while (Head<Tail && h[i]<=h[Queue[Tail-1]]) Tail--; L[i]=i-Queue[Tail-1]-1; Queue[Tail++]=i; } Queue[0]=n+1; Head=0,Tail=1; for (i=n;i>=1;i--) { while (Head<Tail && h[i]<=h[Queue[Tail-1]]) Tail--; R[i]=Queue[Tail-1]-i-1; Queue[Tail++]=i; } long long MaxArea=0; for (i=1;i<=n;i++) { long long Area=(L[i]+R[i]+1)*h[i]; if (Area>MaxArea) MaxArea=Area; } cout<<MaxArea;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
