第十四届蓝桥杯省赛C++编程题解;最大的矩形纸片

2023-05-18 09:15:20    动态资讯   

一张半边参差不齐的网格纸(网格边长均为1),有一边是完整没有破损的。现要从中剪出一片面积最大的矩形纸片。

给定网格纸中完整边的长度N1N1000000),以及网格中每一列残存部分的高度(1≤高度≤10000),输出能够剪出的最大矩形纸片面积。

例如:N=6,每一列残存部分的高度依次为321452,如下图所示:

可以发现,沿着红色框可以剪出的矩形纸片面积最大,为8,所以输出8

 

【输入描述】

第一行输入一个正整数N1N1000000),表示纸片完整边的长度

第二行输入N个正整数(1≤正整数≤10000),表示每列格子残存部分的高度,两个正整数之间用一个空格隔开

【输出描述】

输出一个正整数,表示能够剪出的最大矩形纸片面积

 

【样例输入】

6

3 2 1 4 5 2

【样例输出】

8

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1000006],ans;//a[i]保存了第i列的高度 
int st[1000006],top,t;//st为单调递增栈,保存高度递增的柱子编号 
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    scanf("%d",a+i);
  for(int i=1;i<=n;i++)
  {
    if(a[i]>a[st[top]])//如果当前柱子高度比栈顶柱子高,则列编号进栈 
      st[++top]=i;
    else
    {
      //当栈不空且栈顶柱子高于当前柱子时,弹出栈顶元素 
      while(top>0&&a[st[top]]>=a[i]) 
      {
        t=st[top--];
        ans=max(ans,(i-st[top]-1)*a[t]);//更新最大高度 
      }
      //当前列编号进栈 
      st[++top]=i;
    }
  }
  //遍历完序列后,弹出栈内剩余柱子
  //栈内剩余柱子的右边界默认为序列的最大长度 
  while(top>0)
  {
    t=st[top--];
    ans=max(ans,(n-st[top])*a[t]);
  }
  cout<<ans;
  return 0; 
}