CCF真题之最大矩形

时间:2021-09-07 20:47:48

201312-3

问题描述
  在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。
CCF真题之最大矩形   
请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形如下图所示的阴影部分,面积是10。
CCF真题之最大矩形
输入格式
  第一行包含一个整数n,即矩形的数量(1 ≤ n ≤ 1000)。   
      第二行包含n 个整数h1, h2, … , hn,相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。
输出格式
  输出一行,包含一个整数,即给定直方图内的最大矩形的面积。
样例输入
6 3 1 6 5 2 3
样例输出
10
 
源代码:
#include <iostream>
using namespace std;
int main()
{
 int n,i,j,h,s,max,a[1001];
 cin>>n;
 for(i=0;i<n;i++)
 cin>>a[i];
 max=0;
 //从第一个矩形开始,往右扫描,若后面的矩形高度比第一个低,则h为较低的那个值,不断发生改变
 for(i=0;i<n;i++)
 {
  h=a[i];
  for(j=i;j<n;j++)
  {
     if(a[j]<h)
      h=a[j];
      s=h*(j-i+1);   //矩形面积=长X宽
      if(s>max)
      max=s;
  } 
 }
 cout<<max<<endl; 
 return 0;
}

CCF真题之最大矩形的更多相关文章

  1. CCF真题之最优灌溉

    201412-4 问题描述 雷雷承包了很多片麦田,为了灌溉这些麦田,雷雷在第一个麦田挖了一口很深的水井,所有的麦田都从这口井来引水灌溉. 为了灌溉,雷雷需要建立一些水渠,以连接水井和麦田,雷雷也可以利 ...

  2. CCF真题之画图

    201409-2 问题描述 在一个定义了直角坐标系的纸上,画一个(x1,y1)到(x2,y2)的矩形指将横坐标范围从x1到x2,纵坐标范围从y1到y2之间的区域涂上颜色. 下图给出了一个画了两个矩形的 ...

  3. CCF真题之窗口

    201403-2 问题描述 在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标轴分别平行的矩形区域.窗口的边界上的点也属于该窗口.窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示 ...

  4. CCF真题Z型输出

    #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> ...

  5. CCF模拟题 最大的矩形

    最大的矩形 时间限制: 1.0s 内存限制: 256.0MB     问题描述 在横轴上放了n个相邻的矩形,每个矩形的宽度是1,而第i(1 ≤ i ≤ n)个矩形的高度是hi.这n个矩形构成了一个直方 ...

  6. CCF真题之命令行选项

    201403-3 问题描述 请你写一个命令行分析程序,用以分析给定的命令行里包含哪些选项.每个命令行由若干个字符串组成,它们之间恰好由一个空格分隔.这些字符串中的第一个为该命令行工具的名字,由小写字母 ...

  7. CCF真题之节日

    201503-3 问题描述 有一类节日的日期并不是固定的,而是以“a月的第b个星期c”的形式定下来的,比如说母亲节就定为每年的五月的第二个星期日. 现在,给你a,b,c和y1, y2(1850 ≤ y ...

  8. CCF真题之字符串匹配

    201409-3 问题描述 给出一个字符串和多行文字,在这些文字中找到字符串出现的那些行.你的程序还需支持大小写敏感选项:当选项打开时,表示同一个字母的大写和小写看作不同的字符:当选项关闭时,表示同一 ...

  9. CCF真题之网络延时

    201503-4 问题描述 给定一个公司的网络,由n台交换机和m台终端电脑组成,交换机与交换机.交换机与电脑之间使用网络连接.交换机按层级设置,编号为1的交换机为根交换机,层级为1.其他的交换机都连接 ...

随机推荐

  1. swift3&period;0变化总结

    Swift 3.0 做出的改变很大,在这篇文章中,我将尽我所能,利用代码样例给大家解释Swift 3.0最重要(要命)的改变,希望大家能够做好升级Swift 3.0 的准备.Swift 3.0的改变不 ...

  2. HDU 1556 线段树或树状数组,插段求点

    1.HDU 1556  Color the ball   区间更新,单点查询 2.题意:n个气球,每次给(a,b)区间的气球涂一次色,问最后每个气球各涂了几次. (1)树状数组 总结:树状数组是一个查 ...

  3. 深入剖析HADOOP程序日志

    深入剖析HADOOP程序日志 前提 本文来自于 博客园 逖靖寒的世界 http://gpcuster.cnblogs.com 了解log4j的使用. 正文 本文来自于 博客园 逖靖寒的世界 http: ...

  4. 用C&num;读取,写入ini文件

    [DllImport("kernel32.dll")] private static extern bool WritePrivateProfileString(string se ...

  5. WebGL 3D 电信机架实战之数据绑定

    前言 在前端中,视图层和数据层需要进行单向或者双向数据绑定,大家都已经不陌生了,有时候 2D 做的比较顺了之后,就会想要挑战一下 3D,不然总觉得痒痒的.这个 3D 机架的 Demo 我觉得非常有代表 ...

  6. Scyther-Semantics and verification of Security Protocol

    1 .本书前一节主要是介作者自己的生平经历(读完感觉作者是个神童),目标明确作者13岁代码已经写的很溜了.自己也开了网络公司,但是后面又专注于自己的计算机基础理论,修了哲学的博士学位(不得不说很多专业 ...

  7. 卸载阿里云自带svn

  8. python偏函数的运用

    摘要:python的设计核心原则就是简洁——在这种原则的指导下,诞生了lambda表达式和偏函数:二者都让函数调用变得简洁.本文主要为你介绍偏函数的应用. 1.为什么要使用偏函数 如果我们定义了一个函 ...

  9. django登录功能(简单在POST请求)

    第一  先在templates中创立index.html !DOCTYPE html> <head> <meta charset="UTF-8"> & ...

  10. Ansible 从远程主机添加或删除MySQL数据库

    mysql_db - 从远程主机添加或删除MySQL数据库. 概要 要求(在执行模块的主机上) 选项 例子 笔记 状态 支持 概要 从远程主机添加或删除MySQL数据库. 要求(在执行模块的主机上) ...