Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 32868Accepted: 10711

DescriptionA histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles: 

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

InputThe input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,…,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

OutputFor each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

HintHuge input, scanf is recommended.

思路

这其实是一道单调栈模板题。先思考一个问题,如果题目中的矩形的高度都是单调递增的,如何得到最优解?显然有一个贪心的策略,就是以每一个矩形的高度作为最终大矩形的高度,看最宽能是多少,然后统计最优解。
但如果进来的下一矩形比上一个低,它其实相当于限制了之前矩形的高度,那么之前矩形比这个矩形高出的高度在以后的统计中就没有丝毫用处了,如果我们在这个时候把以之前矩形的高度作为最终高度的答案统计掉,那么反正以后的统计和上一个矩形没有关系,还不如把他删除。
这样,我们实际上就得到了单调栈的模型,只需要维护一个单调栈,在维护单调性的弹出操作时统计宽度,更新答案即可在O(n) O(n)O(n)实际内得到最优解。
为了方便把最后剩下的,以及单调递增的矩形也统计进去,我们假设a[n+1]的位置有一个高度为0的矩形,最后将它加入单调栈时他会将所有矩形都弹出,那么答案也就完成最后的更新了。 (转自https://blog.csdn.net/Prasnip_/article/details/83690038

代码

#include <iostream>
#include <string.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const int mod=1e9+7;
const int maxm=1e3+10;
using namespace std;
int a[maxn];
int sta[maxn];
int width[maxn];
int main(int argc, char const *argv[])
{
    #ifndef ONLINE_JUDGE
        freopen("/home/wzy/in.txt", "r", stdin);
        freopen("/home/wzy/out.txt", "w", stdout);
        srand((unsigned int)time(NULL));
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin>>n&&n)
    {
        ms(sta,0);
        ms(width,0);
        ms(a,0);
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int top=0;
        ll ans=0;
        for(int i=1;i<=n+1;i++)
        {
            if(sta[top]<a[i])
                sta[++top]=a[i],width[top]=1;
            else
            {
                int res=0;
                while(sta[top]>a[i])
                {
                    res+=width[top];
                    ans=max(ans,1LL*res*sta[top]);
                    top--;
                }
                sta[++top]=a[i];width[top]=res+1;
            }
        }
        cout<<ans<<endl;
    }
    #ifndef ONLINE_JUDGE
        cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
    #endif
    return 0;
}

发表评论

共有 0 条评论