【题目描述】 最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，且1<=Hi<=1,000,000,000，并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。 【输入格式】 第一行是一个数n (n<= 400,000 ） 第二行是n个数，分别表示每个建筑物高度H1,H2…HN，且1<=Hi<=1,000,000,000。 【输出格式】 输出文件 ad.out 中一共有一行，表示广告牌的最大面积。 【 样例输入】 6 5 8 4 4 8 4 【样例输出】 24 【分析】 首先可以想到，在广告覆盖的楼房中，最矮的楼房（并不是指所有楼房中最矮的那个）一定被广告完全覆盖了。所以可以枚举最矮的楼房，求出向左、向右分别可以延伸多远（即大于等于该楼房），然后打擂台即可。 用单调队列预处理向左、向右分别延伸的距离可以优化程序。
#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;}新闻热点
疑难解答
