Codeforces 1841E Fill the Matrix

题目来自 Codeforces Educational Round #150 (Div.2) E。link

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

原题题面讲的有点复杂，这里采用 @灵茶山艾府 的翻译：

给出一个 \(n\times n\) 的矩阵，第 \(i\) 列的前 \(a_i\) 行是白色，其余行是黑色 (初始局面)。要求从中选出至多 \(m\) 个白色格子，再将剩余的格子涂黑。

长为 \(x\) 的水平连续白色格子对答案的贡献是 \(x-1\)，求答案的最大值。

Tutorial

选择一个长度为 \(k\) 的水平连续段对答案的贡献为 \(k-1\)。若选择了 \(s\) 段，答案为 \(\sum_{i=1}^s (k_i-1)=m-s\)。最大化答案意味着最小化选择的段数 \(s\)。

若要使选择的段数 \(s\) 最小，我们需要尽量选择最长的段。问题转化为在初始局面中找到这些最长的水平连续段。在矩阵中连续段的数量是 \(O(n^2)\) 级别的，使用暴力显然行不通。

考虑维护 \(cnt_i\)，表示长度为 \(i\) 的连续段的个数。对于一个初始的全白矩阵，\(cnt_n=n\)。

考虑加入一列高度为 \(a_i\) 的黑色段对 \(cnt\) 的影响：首先，\(a_i\) 个长度为 \(n\) 的连续段会被隔开，\(cnt_n=n-a_i\)；同时，两种新长度的连续段将会被创造，(左侧) \(cnt_{i-1}=a_i\)，(右侧) \(cnt_{n-i}=a_i\)。

根据分治原则，易发现由高到低处理黑色列是最合适的：这样能够保证每次加入一个黑色列，对 \(cnt\) 的维护方法始终一致，即 1. 移除特定长度的连续段 2. 加入(至多)两种新长度的连续段。

设当前黑色列的高度为 \(v\)，位于第 \(i\) 列，其左边界为第 \(pre\) 列，右边界为第 \(suf\) 列。由于我们由高到低进行处理，其左边界与右边界列一定不比它低。那么 \(cnt_{suf-pre-1}\) 减小 \(v\)，\(cnt_{i-pre-1}\) 与 \(cnt_{suf-i-1}\) 增加 \(v\)。

此时问题转化为动态维护某一列左右的边界，用一个 set 即可实现。set 初始插入 \(0\) 与 \(n+1\) 作为边界哨兵。

当所有列都成功加入后，我们得到了初始局面下的 \(cnt\) 数组。那么答案就呼之欲出了：由 \(n\) 到 \(1\) 倒序枚举长度，尽量选择当前最长的连续段用来填充 \(m\)，并计算所用的连续段数量 \(s\)。答案即为 \(m-s\)。

Code Implementation

得到 \(cnt\) 数组后倒序填充 \(m\) 求答案的过程还有点小坑，记得讨论代码中标注的情况 (*)

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

const int MAX_N = 2e5 + 10;

struct column {
    int ind, val;
    bool operator < (const column& x) const { return ind < x.ind; }
} col[MAX_N];

long long cnt[MAX_N];

bool cmp(column& x, column& y) { return x.val > y.val;  }

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long m;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            col[i].ind = i;
            cin >> col[i].val;
            cnt[i] = 0;
        }
        cin >> m;
        sort(col + 1, col + n + 1, cmp);
        
        set<column> st;
        st.insert(column{0, n});
        st.insert(column{n + 1, n});

        cnt[n] = n;
        for (int i = 1; i <= n; ++i) {
            set<column>::iterator it = st.insert(col[i]).first;
            --it;
            int pre_ind = it->ind;
            ++it, ++it;
            int suf_ind = it->ind;
            int cur_ind = col[i].ind, cur_val = col[i].val;
            cnt[suf_ind - pre_ind - 1] -= cur_val;
            cnt[cur_ind - pre_ind - 1] += cur_val;
            cnt[suf_ind - cur_ind - 1] += cur_val;
        }

//        for (int i = 1; i <= n; ++i) cout << i << " " << cnt[i] << endl;

        long long s = 0, tmp_m = m;
        for (int i = n; i >= 1; --i) {
            if (!cnt[i])    continue;
            long long cur_s = min(cnt[i], tmp_m / i);
            tmp_m -= cur_s * i;
            s += cur_s;
            if (!tmp_m) break;
            if (cur_s < cnt[i] && tmp_m < i) {    // *
                s++;
                break;
            }
        }
        cout << m - s << endl;
    }

    return 0;
}