【CCF-CSP】(13年12月)最大的矩形
2021/8/17 23:08:32
本文主要是介绍【CCF-CSP】(13年12月)最大的矩形,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述
在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。
请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。
输入格式
第一行包含一个整数n,即矩形的数量(1 ≤ n ≤ 1000)。
第二行包含n 个整数h1, h2, … , hn,相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。
输出格式
输出一行,包含一个整数,即给定直方图内的最大矩形的面积。
样例输入
6 3 1 6 5 2 3
样例输出
10
算法
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int n; int h[N]; int main() { cin >> n; for (int i = 1; i <= n; i ++ ) cin >> h[i]; int res = 0; for (int i = 1; i <= n; i ++ ) { int l = i, r = i; while (l >= 1 && h[l] >= h[i]) l --; while (l <= n && h[r] >= h[i]) r ++; res = max(res, h[i] * (r - l - 1)); } cout << res << endl; return 0; }
这篇关于【CCF-CSP】(13年12月)最大的矩形的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享