poj2082栈的应用之给定每个矩形的长和宽求可以形成的最大矩形

发表于   |   分类于   |  

题目链接

Terrible Sets

题目描述(Description)

Terrible Sets（糟糕的集合）

假设N是自然数集合，R是表示所有实数的集合，wi,hi(i=1…n)是N里的一些元素，w0=0.
定义集合B={|x,y $\in$ R,存在i>0使得0<=y<=hi,$\prod{0\leqj\leq(i-1)}wj \leq x \leq \prod{0\leqj\leqi}wj$}

定义集合S={A|A=WH,W,H$\in$ $R^+$,在N中存在x0,y0使得集合T={|x,y$\in$ $R^+$,x0 <= x <= x0 +W, y0 <= y <= y0 + H} 包含于集合B}

你的任务是求S的最大值。

题目大意：这个题目描述的好绕，其实大意是：紧贴想x轴有一些相互挨着的矩形，给定连续的宽和长，求出最大的连续矩形的面积。

样例输入

3
1 2
3 4
1 2
3
3 4
1 2
3 4
-1

样例输出

12
14

分析(Analysis)

这道题的题目描述实在太晦涩。

直接看样例：

Case#1：

Case#2:

  1. 可以用一个栈stact<Node>s模拟，将矩形入栈，如果矩形的高度递增，即rect.h大于栈顶矩形的高度，则将此矩形入栈；
  2. 如果矩形的高度比当前栈顶矩形的高度小，此时该矩形不入栈，但是要计算此高度的矩形与之前入栈的矩形所能围成的最大矩形，矩形高度已知为rect.h，主要计算到达的最大宽度。最大宽度设为width,初始化为0，如果栈非空&&s.top().h>rect.h,则width+=s.top.w，然后把新的大矩形压入栈；
  3. 注意到测试2的情况，最后还要扫描所有入栈的矩形，否则如果最后一个入栈的矩形高度比栈顶矩形高度大小，则会少加一部分面积。

代码(Code)

#include<cstdio>
#include<stack>
using namespace std;
struct Node{
    int w,h;//宽和高 
}rect;
int main()
{
    int n,ans,curArea,width;
    while(scanf("%d",&n)&&n!=-1)
    {
        ans=0;
        stack<Node> s;
        while(n--)
        {
            scanf("%d%d",&rect.w,&rect.h);
            if(s.empty()||rect.h>=s.top().h){
                s.push(rect);//如果栈为空或矩形高度递增，则压入栈； 
            }
            else{
                width=0;
                curArea=0;
                while(!s.empty()&&s.top().h>rect.h)
                {//计算最大宽度 
                    width+=s.top().w;
                    curArea=width*s.top().h;
                    if(curArea>ans)
                        ans=curArea;
                     s.pop();
                }
                //将新的大矩形压入栈
                width+=rect.w;
                rect.w=width;
                 s.push(rect);
            }
        }
        width=0;
        curArea=0;
        while(!s.empty())
        {//再次扫面看是否存在更大的矩形（例如测试样例2所示） 
            width+=s.top().w;
            curArea=s.top().h*width;
            if(curArea>ans)
                ans=curArea;
            s.pop();
        }
        printf("%d\n",ans);
    }
    return 0;
}