欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

【UOJ 48】最大矩形面积(修正版)

发布时间:2024/7/5 编程问答 4 豆豆
如意编程网 收集整理的这篇文章主要介绍了 【UOJ 48】最大矩形面积(修正版) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

【题目描述】:

地面上从左到右并排紧挨着摆放多个矩形,已知这此矩形的底边宽度都为1,高度不完全相等。求在这些矩形包括的范围内能得到的面积最大的矩形,打印出该面积。所求矩形可以横跨多个矩形,但不能超出原有矩形所确定的范围。

如 n = 7, 序列为2 1 4 5 1 3 3

_ _ _ | | _ | | | || | _ _ |H||H| _ _ _ | || | | || | _ |H||H| | || | | | _ | || | _ | || | | | _ |H||H| _ | || | |_||_||_||_||_||_||_| |_||_||H||H||_||_||_|

最大面积:8

【输入描述】:

输入有多组数据,每组数据一行:

第一个数N,表示矩形个数

后面跟N个正整数,第i个正整数hi表示第i个矩形的高度。

最后一行,以一个单独的0结束。

【输出描述】:

每组输入数据一行,一个数表示最大矩形面积。

【样例输入】:

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

【样例输出】:

8 4000

【时间限制、数据范围及描述】:

时间:1s 空间:64M

30 %: 1<=N<=100

60 %: 1<=N<=1,000

100%: 1<=N<=500,000,0<=hi<=1,000,000,000

 

题解:问题可简化为两个子问题,每找到一个点,查找左第一个比他大的,右边第一个比她大的。

(这里用单调栈即可)两坐标之差再乘上i的高度即可得出答案。

#include <iostream> #include <cstdio> #include <cstring> #define MAX_N 500005 using namespace std;int main() {int n;while(~scanf("%d",&n)&&n){int a[MAX_N];int l[MAX_N],r[MAX_N];for(int i=1;i<=n;i++)scanf("%d",&a[i]);l[0]=0,l[n+1]=0;for(int i=1;i<=n;i++){int k=i-1;if(a[i]<=a[k]){while(k>0&&a[i]<=a[k]) k=l[k]-1; }l[i]=k+1;}for(int i=n;i>=1;i--){int k=i+1;if(a[i]<=a[k]){while(k<n+1&&a[i]<=a[k]) k=r[k]+1;}r[i]=k-1;}long long maxn=-1;for(int i=1;i<=n;i++){long long s=(long long)(r[i]-l[i]+1)*a[i];if(s>maxn) maxn=s;}printf("%lld\n",maxn);}return 0; }

 

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11205744.html

总结

以上是如意编程网为你收集整理的【UOJ 48】最大矩形面积(修正版)的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。