SiriBlog

siriyang的个人博客


  • 首页

  • 排行榜

  • 标签115

  • 分类37

  • 归档319

  • 关于

  • 搜索

CCF-CSP/201312-3最大的矩形

发表于 2020-01-27 更新于 2021-10-29 分类于 计算机 , 算法题 , CCF-CSP 阅读次数: Valine:
本文字数: 1k 阅读时长 ≈ 1 分钟

CCF-CSP题目汇总

题目

试题编号: 201312-3
试题名称: 最大的矩形
时间限制: 1.0s
内存限制: 256.0MB

问题描述

  在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 $\le i \le$ n)个矩形的高度是$h_i$。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

  请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。

输入格式

  第一行包含一个整数n,即矩形的数量(1 $\le n \le$ 1000)。
  第二行包含n 个整数$h_1, h_2, … , h_n$,相邻的数之间由空格分隔。(1 $\le h_i \le$ 10000)。$h_i$是第i个矩形的高度。

输出格式

  输出一行,包含一个整数,即给定直方图内的最大矩形的面积。

样例输入

1
2
6
3 1 6 5 2 3

样例输出

10

解答

解析

  从1开始逐渐加高高度直到达到最大高度,分别计算个高度下存在的连续矩形面积。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

int n,mh=0;
int res=0;
vector<int> num;

cin>>n;

for(int i=0;i<n;i++){
int t;
cin>>t;
mh=max(mh,t);
num.push_back(t);
}

for(int i=1;i<=mh;i++){
int t=0;
for(int j=0;j<n;j++){
if(num[j]>=i)
t+=i;
else{
res=max(res,t);
t=0;
}
}
res=max(res,t);
}

cout<<res;

return 0;
}
-------- 本文结束 感谢阅读 --------
相关文章
  • CCF-CSP:201409-3字符串匹配
  • CCF-CSP:201403-3命令行选项
  • CCF-CSP:201403-2窗口
  • CCF-CSP:201403-1相反数
  • CCF-CSP/201409-2画图
觉得文章写的不错的话,请我喝瓶怡宝吧!😀
SiriYang 微信支付

微信支付

SiriYang 支付宝

支付宝

  • 本文标题: CCF-CSP/201312-3最大的矩形
  • 本文作者: SiriYang
  • 创建时间: 2020年01月27日 - 14时01分
  • 修改时间: 2021年10月29日 - 18时10分
  • 本文链接: https://blog.siriyang.cn/posts/20200127145853id.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
算法题 CCF-CSP
CCF-CSP:201403-3命令行选项
C/C++参考文档:C Time & Date
  • 文章目录
  • 站点概览
SiriYang

SiriYang

努力搬砖攒钱买镜头的摄影迷
319 日志
33 分类
88 标签
RSS
GitHub E-Mail
Creative Commons
Links
  • 友情链接
  • 作品商铺

  1. 题目
    1. 问题描述
    2. 输入格式
    3. 输出格式
    4. 样例输入
    5. 样例输出
  2. 解答
    1. 解析
    2. 代码
蜀ICP备19008337号 © 2019 – 2025 SiriYang | 1.7m | 25:41
0%