app怎样下载安装,广州建站优化公司,模板网官网,网页制作的论文真题 第十四届省赛 编程题 第5题 工人砌了一面奇特的砖墙#xff0c;该墙由N列砖组成#xff08;1≤N≤1e6#xff09;#xff0c;且每列砖的数量为Ki#xff08;1≤Ki≤1e4#xff0c;相邻砖块之间无缝隙#xff09;#xff0c;每块砖的长宽高都为1。小蓝为了美化这面…真题 第十四届省赛 编程题 第5题 工人砌了一面奇特的砖墙该墙由N列砖组成1≤N≤1e6且每列砖的数量为Ki1≤Ki≤1e4相邻砖块之间无缝隙每块砖的长宽高都为1。小蓝为了美化这面墙需要在这面墙中找到一块面积最大的矩形用于涂鸦那么请你帮助小蓝找出最大矩形并输出其面积。 例如N6表示这面墙有6列每列砖的数量依次为3、2、1、5、6、2如下图 图中虚线部分是一块面积最大的矩形其面积为10. 输入描述 第一行输入一个正整数N1≤N≤1e6表示这面砖墙由N列砖组成 第二行输入N个正整数Ki1≤Ki≤1e4依次表示每列砖的数量正整数之间以一个空格隔开 输出描述 输出一个正整数表示最大矩形的面积 样例输入 6 3 2 1 5 6 2 样例输出 10 解题思路
1.递归标准解法
找到最矮的列分别计算左中右三个面积分治取其最大。 中最矮列的列高*本区域的宽度贪心假设 左最矮列左侧区域的最大矩形递归调用 右最矮列右侧区域的最大矩形递归调用
2.伸展娃儿创新
遍历每一列分别计算此列为中心向两侧延展直至遇到较矮的列所形成的矩形的面积。 各面积存入列表取其最小值。
代码
思路一 递归版
def tj1(wall):iwall.index(min(wall))sLtj1(wall[:i]) if i0 else 0sRtj1(wall[i1:]) if ilen(wall)-1 else 0return max(wall[i]*len(wall),sL,sR)
思路二伸展版
def tj2(wall):sL[]for i in range(len(wall)):s1; hwall[i]for j in range(i,0,-1):if(hwall[j-1]):si-j; breakelse:si-1for j in range(i,len(wall)-1):if(hwall[j1]):sj-i; breakelse:slen(wall)-1-isL.append(s*h)return max(sL) 增加一个用while代替for...else的版本
def tj2w(wall): # while版sMax0; Nlen(wall)for i in range(N):w1; hwall[i]jiwhile(j0 and hwall[j-1]): j-1wi-jjiwhile(jN-1 and hwall[j1]): j1wj-isNeww*hif(sNewsMax): sMaxsNewreturn sMax
测试代码
def timeit(num100):t1[];t2[];size[]for i in range(num):Krandom.choices(range(1,1000001),krandom.randint(1,10000)); Nlen(K)size.append(N)t0time.time()anstj2(K)t2.append(time.time()-t0)t0time.time()anstj1(K)t1.append(time.time()-t0)return t1,t2,size
结论 两种思路都很容易实现和调试成功从用时看标准版整体稍多于娃儿的思路的1/2仅2%的用例娃儿胜出不排除python的time模块计时不准。
但从孩子的学习成果来看我还是感到非常欣慰特别是python to C时很显然伸展版的思路更契合不用做列表的切片
