题解：CF1841E Fill the Matrix

Ambrosia · 2024-04-09 14:25:32 · 题解

题目大意

有一个 n 行 n 列的矩阵，行和列都从 1 到 n 编号。对于第 i 列，第 1 \sim a_i 个格子是黑色的，其余格子是白色的。

你可以把 1 \sim m 共 m 个整数放到矩阵里，满足两条规则：

1. 每个格子包含至多一个整数。
2. 黑色格子不能包含整数。

一个矩阵的美丽程度是满足这样的格子个数：该格子自身包含一个数 j，且它右边与它相邻的格子包含的数为 j + 1。

请求出矩阵的最大美丽值。

多组数据，n 之和不超过 2 \times 10^5，请注意 m 的大小可能超过 32 位整数所存储的范围。

题目思路

运用单调栈维护一下，挺水的。

AC Code

#include <bits/stdc++.h>

#define endl '\n'
#define int long long
#define inf 0x3f3f3f3f

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")//这五行纯属个人习惯，可以不要

using namespace std;

int n;

struct nood {
    int s, c;
};

stack<nood> a;
map<int, int> mp;
vector<int> b;
int T;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);//这三行也纯属个人习惯，用来加速cin、cout的

    cin >> T;

    while (T--) {
        while (!a.empty()) {
            a.pop();
        }

        b.clear();
        mp.clear();
        cin >> n;

        for (int i = 1; i <= n; i++) {
            int temp;
            cin >> temp;
            int tep = 0;
            int s = 0;

            while (!a.empty() && a.top().c > n - temp) {
                if (s == 0) {
                    tep = a.top().c;
                } else if (tep > a.top().c) {
                    if (mp.find(s) == mp.end()) {
                        b.push_back(s);
                    }

                    mp[s] += tep - a.top().c;
                    tep = a.top().c;
                }

                s += a.top().s;
                a.pop();
            }

            if (s != 0) {
                if (mp.find(s) == mp.end()) {
                    b.push_back(s);
                }

                mp[s] += tep - (n - temp);
            }

            nood temmp;
            temmp.c = n - temp;
            temmp.s = s + 1;
            a.push(temmp);
        }

        int tep = 0;
        int s = 0;

        while (!a.empty()) {
            if (s == 0) {
                tep = a.top().c;
            } else if (tep > a.top().c) {
                if (mp.find(s) == mp.end()) {
                    b.push_back(s);
                }

                mp[s] += tep - a.top().c;
                tep = a.top().c;
            }

            s += a.top().s;
            a.pop();
        }

        if (mp.find(s) == mp.end()) {
            b.push_back(s);
        }

        mp[s] += tep;
        sort(b.begin(), b.end());
        int k;
        int ans = 0;
        cin >> k;
        int i;

        for (i = b.size() - 1; i >= 0; i--) {
            if (k < mp[b[i]]*b[i]) {
                break;
            }

            ans += (mp[b[i]] * (b[i] - 1));
            k -= mp[b[i]] * b[i];
        }

        if (i >= 0) {
            ans += k / b[i] * (b[i] - 1);

            if (k % b[i]) {
                ans += k % b[i] - 1;
            }
        }

        cout << ans << endl;
    }

    return 0;
}