【t009】最大矩形面积

Time Limit: 2 second

Memory Limit: 32 MB

【问题描述】

在x轴上水平放置着N个矩形，每个矩形都有相同的宽度，但是它们的高度并不相同。

比如，图1包含的矩形的高分别为2，1，4，5，1，3，3单位长度，矩形的宽为1单位长度。

你的任务就是计算柱状图中以x轴为底边的最大矩形的面积。图2阴影部分就是上述例子的最大矩形面积。

【输入格式】

输入数据的第一行是一个整数N(1≤N≤100,000)，表示柱状图包含N个矩形。紧接着N个整数h1,...,hn(0≤hi≤20,000, 1≤i≤N)，表示柱状图中按从左到右顺序给出的矩形的高度。矩形的宽度为1。

【输出格式】

输出一行一个整数S，表示以x轴为底边的最大矩形的面积。

【输入样例1】

7 2 1 4 5 1 3 3

【输出样例1】

【输入样例2】

4 1000 1000 1000 1000

【输出样例2】

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t009

【题解】

方法是枚举第i个矩形为所有矩形中最低点;看看往左往右能取多少个矩形;

用一个单调队列搞, 处理出第i个矩形能往前取多远，能往后取多远;

每次枚举到第i个矩形的时候先和前一个矩形的高度比较；

如果比前一个高,则以第i个矩形为最低的情况最左只能取到第i个本身;并把这个矩形加入到单调队列中(单增);

如果比前一个矮，那么就往单调队列中的前面找到第一个比第i矩形矮的矩形,并在这个过程中不断把队尾比它大的元素pop掉;

可以看到，②号矩形前面的两个矩形都比②号高，而②号后面如果还有一个矩形比②号低，那么它往前找比它低的矩形的时候，中间那两个矩形就没必要再找了，直接跳过就好;

如上图，中间那3个矩形也可以划掉了;

可以看到我们在维护一个单调队列；

程序1是单调队列(100分);

程序2是用线段树+二分优化的枚举(要3s才能过全部数据,所以只得70分);

【完整代码】

/*

    程序1

*/

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

void rel(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t) && t!='-') t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void rei(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)&&t!='-') t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

const int MAXN = 1e5+100;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

int n;

int a[MAXN],l[MAXN],r[MAXN];

int len,f[MAXN];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    while (scanf("%d",&n)!=EOF)

    {

        rep1(i,1,n)

            scanf("%d",&a[i]);

        rep1(i,1,n)

        {

            if (len==0)

            {

                f[++len] = i;

                l[i]=1;

            }

            while (len >=1 && a[i]<=a[f[len]]) len--;

            if (len==0)

            {

                f[++len] = i;

                l[i] = 1;

            }

            else

            {

                l[i] = f[len]+1;

                f[++len] = i;

            }

        }

        len = 0;

        rep2(i,n,1)

        {

            while (len >=1 && a[i]<=a[f[len]]) len--;

            if (len==0)

            {

                f[++len] = i;

                r[i] = n;

            }

            else

            {

                r[i] = f[len]-1;

                f[++len] = i;

            }

        }

        int ans = 0;

        rep1(i,1,n)

        {

            int len = r[i]-l[i]+1;

            ans = max(len*a[i],ans);

        }

        printf("%d\n",ans);

    }

    return 0;

}

/*

    程序2

*/

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

void rel(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t) && t!='-') t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void rei(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)&&t!='-') t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

const int MAXN = 1e5+10;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

int n,nn=0;

int a[MAXN],mi[MAXN<<2];

void build(int l,int r,int rt)

{

    if (l==r)

    {

        scanf("%d",&a[++nn]);

        mi[rt] = a[nn];

        return;

    }

    int m = (l+r)>>1;

    build(lson);

    build(rson);

    mi[rt] = min(mi[rt<<1],mi[rt<<1|1]);

}

int Q(int L,int R,int l,int r,int rt)

{

    if (L<=l && r <=R)

        return mi[rt];

    int temp1 = 21e8,temp2 = 21e8;

    int m = (l+r)>>1;

    if (L <= m)

        temp1 = Q(L,R,lson);

    if (m < R)

        temp2 = Q(L,R,rson);

    return min(temp1,temp2);

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    int ans = 0;

    scanf("%d",&n);

    build(1,n,1);

    rep1(i,1,n)

    if (a[i]*n>ans)

    {

        int l,r,ans1=-1,ans2=-1;

        l = 1,r = i-1;

        while (l<=r)

        {

            int m = (l+r)>>1;

            int d = Q(m,r,1,n,1);

            if (d>=a[i])

                ans1 = m,r = m-1;

            else

                l = m+1;

        }

        l = i+1,r = n;

        while (l<=r)

        {

            int m = (l+r)>>1;

            int d = Q(l,m,1,n,1);

            if (d>=a[i])

                ans2 = m,l = m+1;

            else

                r = m-1;

        }

        int ll,rr;

        ll = (ans1==-1)?i:ans1;

        rr = (ans2==-1)?i:ans2;

        int s = (rr-ll+1)*a[i];

        ans = max(ans,s);

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

【t009】最大矩形面积

最新文章

热门文章