A37453. 最大的矩形纸片
填空题
困难
知识点
题目描述
最大的矩形纸片
题目描述
编程实现:最大的矩形纸片
一张半边参差不齐的网格纸 (网格边长均为1)，有一边是完整没有破损的。现要从中剪出一片面积最大的矩形纸片。
给定网格纸中完整边的长度N (1<=N<=1000000) ，以及网格中每一列残存部分的高度(1<=高度<=10000)，输出能够剪出的最大矩形纸片面积。
例如: N=6，每一列残存部分的高度依次为3、2、1、4、5、2，如下图所示：
可以发现，沿着红色框可以剪出的矩形纸片面积最大，为8，所以输出8。
输入描述
第一行输入一个正整数N（1≤N≤1000000），表示纸片完整边的长度
第二行输入N个正整数（1≤正整数≤10000），表示每列格子残存部分的高度，两个正整数之间用一个空格隔开
输出描述
输出一个正整数，表示能够剪出的最大矩形纸片面积
样例输入
6
3 2 1 4 5 2
样例输出
8
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int h[N], z[N], y[N], n, maxn = 0, s;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
z[i] = i; //左边界
y[i] = i; //右边界
}//初始化左右边界
//求所有悬线的左边界
for (int i = 1; i <= n; i++) {
while (z[i] > i && h[i] <= h[z[i] - 1]) { //z[i]-1为左边界前一项
z[i] = z[z[i] - 1]; //继承前一项的左边
}
}
//求所有悬线的右边界
for (int i = 1; i <= n; i++) {
while (y[i] < n && h[i] <= h[y[i] + 1]) { //y[i]+1为右边界后一项
y[i] = y[y[i] + 1]; //继承后一项的右边
}
}
//打擂台
for (int i = 1; i <= n; i++) {
s = h[i] * (y[i] - z[i] + 1);
maxn = max(s, maxn);
}
cout << maxn;
return 0;
}
上一题
下一题