Second Large Rectangle

解题思路

先求出每个点上的高，再利用单调栈分别求出每个点左右两边第一个高小于自己的位置，从而而得出最后一个大于等于自己的位置，进而求出自己的位置的高为高，这个点所在的边为底的最大矩形。这些求出的矩形中的最大值即为可求出的最大矩形。而次大值可能是这些矩形之一，也可能是这些矩形的高减1或者宽减1得到的矩形。所以把这些全都记录下来，第二大的即为答案。由于这样求出的矩形会有重复，所以记录一下坐标来去重。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 1005;

int a[N][N], h[N][N];

int l[N][N], r[N][N];

struct T{

    int val, i;

    T(int val, int i): val(val), i(i){}

};

struct R{

    int s, x, y, r;

    R(){}

    R(int s, int x, int y, int r): s(s), x(x), y(y), r(r){}

    bool operator<(const R& a)const{

        if(s != a.s)

            return s < a.s;

        else if(x != a.x)

            return x < a.x;

        else if(y != a.y)

            return y < a.y;

        else

            return r < a.r;

    }

};

int main()

{

    int n, m;

    scanf("%d%d%*c", &n, &m);

    for(int i = 1; i <= n; i ++){

        for(int j = 1; j <= m; j ++){

            char ch = getchar();

            a[i][j] = ch - '0';

        }

        getchar();

    }

    for(int i = 1; i <= n; i ++){

        for(int j = 1; j <= m; j ++){

            if(a[i][j])

                h[i][j] = h[i - 1][j] + 1;

            else

                h[i][j] = 0;

        }

    }

    for(int i = 1; i <= n; i ++){

        stack<T> sta1;

        for(int j = 1; j <= m; j ++){

            while(!sta1.empty() && sta1.top().val >= h[i][j])

                sta1.pop();

            if(!sta1.empty())

                l[i][j] = sta1.top().i + 1;

            else

                l[i][j] = 1;

            sta1.push(T(h[i][j], j));

        }

        stack<T> sta2;

        for(int j = m; j >= 1; j --){

            while(!sta2.empty() && sta2.top().val >= h[i][j])

                sta2.pop();

            if(!sta2.empty())

                r[i][j] = sta2.top().i - 1;

            else

                r[i][j] = m;

            sta2.push(T(h[i][j], j));

        }

    }

    priority_queue<R> pq;

    for(int i = 1; i <= n; i ++){

        for(int j = 1; j <= m; j ++){

            if(!a[i][j])

                continue;

            pq.push(R((r[i][j] - l[i][j] + 1) * h[i][j], i, l[i][j], r[i][j]));

            pq.push(R((r[i][j] - l[i][j]) * h[i][j], i, l[i][j], r[i][j] - 1));

            pq.push(R((r[i][j] - l[i][j] + 1) * (h[i][j] - 1), i, l[i][j], r[i][j]));

        }

    }

    R top;

    if(!pq.empty()){

        top = pq.top();

        pq.pop();

    }

    while(!pq.empty()){

        R t = pq.top();

        pq.pop();

        if(t.s != top.s || t.x != top.x || t.y != top.y || t.r != top.r){

            cout << t.s << endl;

            return 0;

        }

    }

    cout << 0 << endl;

    return 0;

}

巴特西

2019牛客多校第二场H-Second Large Rectangle

Second Large Rectangle

解题思路

代码如下

最新文章

热门文章