首页 > 代码库 > CCF 201312-3 最大的矩形 (暴力，离散化)

CCF 201312-3 最大的矩形 (暴力，离散化)

2024-08-11 02:34:08   214人阅读

问题描述
　　在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。


技术分享
　　请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。
技术分享
输入格式
　　第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。
　　第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。
输出格式
　　输出一行，包含一个整数，即给定直方图内的最大矩形的面积。
样例输入
6
3 1 6 5 2 3
样例输出
10
析：我们可以对它进行离散化，把每个小区间的小矩形都算一下，再更新最大值，O(n^2),复杂度。
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#include <string>#include <cstdlib>#include <cmath>#include <iostream>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <vector>#include <map>#include <cctype>#include <cmath>#include <stack>#define frer freopen("in.txt", "r", stdin)#define frew freopen("out.txt", "w", stdout)using namespace std;typedef long long LL;typedef pair<int, int> P;const int INF = 0x3f3f3f3f;const double inf = 0x3f3f3f3f3f3f;const double PI = acos(-1.0);const double eps = 1e-8;const int maxn = 1e3 + 5;const int mod = 1e9 + 7;const int dr[] = {-1, 1, 0, 0};const int dc[] = {0, 0, 1, -1};const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};int n, m;const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};inline int Min(int a, int b){ return a < b ? a : b; }inline int Max(int a, int b){ return a > b ? a : b; }inline LL Min(LL a, LL b){ return a < b ? a : b; }inline LL Max(LL a, LL b){ return a > b ? a : b; }inline bool is_in(int r, int c){    return r >= 0 && r < n && c >= 0 && c < m;}int h[maxn];int solve(int s, int t){    int ans = INF;    for(int i = s; i < t; ++i)  ans = Min(ans, h[i]);    return ans;}int main(){    cin >> n;    for(int i = 0; i < n; ++i)  scanf("%d", &h[i]);    int ans = 0;    for(int i = 0; i < n; ++i)        for(int j = i; j < n; ++j)            ans = Max(ans, solve(i, j+1) * (j-i+1));    printf("%d\n", ans);    return 0;}

 

CCF 201312-3 最大的矩形 (暴力，离散化)


联系
我们