题解：B4273 [蓝桥杯青少年组省赛 2023] 最大的矩形纸片

· · 题解

形式化题意

给定长度为 n（1\le n \le 10^{6}）的序列 a（1\le a_{i} \le 10^{4}），求一段连续子序列中的最小值乘长度的最大值。

主要思路

考虑二分。我们可以枚举每个 a_{i} 作为一段连续子序列的最小值，为了保证最小值乘长度最大，这段连续子序列的左边界就应该是从 a_{i} 开始使 i 不断减 1 第一个小于 a_{i} 的数的下标加 1；右边界就应该是从 a_{i} 开始使 i 不断加 1 第一个小于 a_{i} 的数的下标减 1。

要求这两个数，可以将所有小于 a_{i} 的数的下标统一放在一个 set，这样就可以形成有序，就可以二分求两个边界了。

时间复杂度

O(n\log n)

注意事项

AC Code

#include<map>
#include<set>
#include<stack>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define gc getchar
#define pc putchar
typedef long long ll;
typedef long double db;
const int N = 1e6 + 10;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------
set<ll> st;
pair<ll, ll> h[N];
// ----------------------------

int main() {
    ll n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i].first;
        h[i].second = i;
    }
    // ----------------------------
    ll idx, ans = 0;
    sort(h + 1, h + n + 1);  // 保证在求 ai 时 set 存的下标对应的数都小于 ai
    for (int i = 1; i <= n; i++) {
        idx = h[i].second;
        if (i == 1) ans = max(ans, h[i].first * n);
        else {
            auto l = st.upper_bound(idx);
            auto r = st.upper_bound(idx);
            if (l == st.begin()) ans = max(ans, h[i].first * (*r - 1));  // 如果没有比 ai 小的数，边界为 1
            else if (r == st.end()) {  // 如果没有比 ai 大的数，边界为 n
                l--;
                ans = max(ans, h[i].first * (n - *l));
            }
            else {
                l--;
                ans = max(ans, h[i].first * (*r - *l - 1));
            }

        }
        st.insert(idx);
    }
    // ----------------------------
    cout << ans;
    return 0;
}