【蓝桥杯省赛真题48】python最大矩形面积 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析

目录

python最大矩形面积

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、 推荐资料

1、蓝桥杯比赛

2、考级资料

3、其它资料

python最大矩形面积

第十四届蓝桥杯青少年组python比赛省赛真题

一、题目要求

（注：input（）输入函数的括号中不允许添加任何信息）

1、编程实现

        工人砌了一面奇特的砖墙,该墙由N列砖组成(1≤N≤106),且每列砖的数量为Ki(1≤Ki≤104,相邻两列砖之间无缝隙),每块砖的长宽高都为1。
        小蓝为了美化这面墙,需要在这面墙中找到一块面积最大的矩形用于涂鸦，那么请你帮助小蓝找出最大矩形，,并输出其面积例如:N=6，表示这面墙有6列，每列砖的数量依次为3、2、1、5、6、2.如下图:

图中虚线部分是一块面积最大的矩形，其面积为10。

2、输入输出

输入描述：第一行输入一个正整数N(1≤N≤10^6)，表示这面砖墙由几列砖组成
第二行输入N个正整数Ki(1≤Ki≤10^4)，表示每列砖的数量，正整数之间以一个空格隔开

输出描述：只有一行，一个整数，即最大矩形的面积!

输入样例：

6
3 2 1 5 6 2

输出样例：

10

二、算法分析

1. 本题的方式解法有很多种，小兔子老师这边采用比较贴合小朋友们的思路方式进行讲解
2. 我们都知道一个矩形的面积等于长乘以宽（或者底乘以高）
3. 而本题中输入的ki其实就是对应的以低i个高为ki，然后以后面每增加一个i对应为宽而构成的矩形
4. 比如，输入的第一个数是3，就可以看做是高为3，底为1的长方形，面积为：3*1
5. 在输入第二个数2的时候，这时候组合而成的矩形高度就是3和2中小的那个值2为高，底为2（2块砖），面积就为：2*2
6. 所以根据上面的推理方式，可以每次以第i（i从第一块开始直到最后一块）块砖为起点，然后依次从第i快开始遍历到后面所有加入的砖，这时候只需要找到加入砖后的最小高，然后乘以加入的砖块数，就是第i轮的最大面积；最后在比较得出这i轮最大面积中最大的那一个值即可

三、程序编写

n = int(input())
lst = list(map(int,input().split()))
maxs = 0;
for i in range(n):
    s1 = lst[i];
    for j in range(i,n):
        s1 = min(s1,lst[j])
        maxs = max(maxs,s1*(j-i+1))
print(maxs)

四、程序说明

1. 首先，我们读取一个整数n作为输入，表示列表lst的长度。
2. 然后，我们读取一个由空格分隔的整数列表lst，并将其转换为一个整数列表。
3. 接下来，我们初始化变量maxs为0，用于存储最大面积。
4. 然后，我们使用双重循环来计算每个可能的子矩形的面积。
5. 外部循环从0到n-1，表示子矩形的左边界。
6. 内部循环从外部循环变量i到n-1，表示子矩形的右边界。
7. 我们定义变量s1并将其初始化为lst[i]，表示子矩形的最小高度。
8. 然后，我们使用一个循环来更新s1的值。
9. 在每次循环中，我们将s1的值更新为s1和lst[j]的较小值，其中j是内部循环的变量。
10. 接下来，我们计算当前子矩形的面积，并将其与maxs进行比较，将较大的值赋给maxs。
11. 最后，我们输出maxs，即最大面积。

五、运行结果

6
3 2 1 5 6 2

10

六、考点分析

难度级别：难，这题相对而言还是有一点小难度，难在题目分析，具体主要考查如下：

1. 学会分析题目，找到解题思路
2. 学会简单的算法知识的应用
3. input函数：Python 中 input() 函数接受一个标准输入数据，返回为 string 类型。
4. int函数：强制将传入对象转换成整数类型
5. split函数：按照指定的分隔符进行分割
6. map函数：将指定的对象按照指定的函数进行迭代，在这里是将时分秒字符串类型数据按int整数类型数字返回输出（相当于多个变量强制类型转化）
7. eval函数：对传入的参数进行运算，如果是一个字符串会转化成对应的序列
8. list函数：强制将参数转化成列表对象
9. 学会列表的相关操作：列表声明、取数、遍历等等
10. 学会for循环的使用：for循环可以遍历任何有序的项及列表元素等等。
11. range函数：rang（a,b），循环的时候是不包括b的，所以我们这个案例中要转变一下，要想包含b，就应该写成range(a,b+1)
12. 学会if...条件判断语句的使用：满足条件才执行相应的程序
13. 学会if...else双分支语句的使用：满足条件执行一种处理程序，不满足执行另一种处理程序
14. print函数：用于打印输出，最常见的一个函数。
15. 充分掌握for循环和列表相关操作函数的使用

PS：方式方法有多种，小朋友们只要能够达到题目要求即可！

七、 推荐资料

• 所有考级比赛学习相关资料合集【推荐收藏】

1、蓝桥杯比赛

• 蓝桥杯python选拔赛真题详解

• 蓝桥杯python省赛真题详解

• 蓝桥杯python国赛真题详解

• 历届蓝桥杯科技素养计算思维真题解析

2、考级资料

• python等级一级真题解析【电子学会】

• python等级二级真题解析【电子学会】

• python等级三级真题解析【电子学会】

• python等级四级真题解析【电子学会】

3、其它资料

• 初学python100例

• 历届蓝桥杯scratch国赛真题解析
• 历届蓝桥杯scratch省赛真题解析
• 历届蓝桥杯scratch STEMA选拔赛真题解析
• 历届蓝桥杯科技素养计算思维真题解析
• 画图-scratch编程考级99图
• 电子学会历年scratch等级考试一级真题解析
• 电子学会历年scratch等级考试二级真题解析
• 电子学会历年scratch等级考试三级真题解析
• 电子学会历年scratch等级考试四级真题解析
• 零基础学习scratch3.0【入门教学 免费】
• 零基础学习scratch3.0【视频教程 114节 免费】