题解：CF2252C Risky Tower

qxsama · 2026-08-08 10:13:15 · 题解

思路

分析题意的两种操作，找到满足其一的最小移除方块数。

1. 任意一行的稳定性 v_i 降低到 0。
2. 任意一行的块数为 0。

根据条件 2，删光这一行的块，答案为列数 m。

思考条件 1，移除第 i 行第 j 列的块后，会让 1 \sim i-1 行的稳定性减少 a_{i,j}。可以从下往上考虑，对于第 i 行，要使稳定性降低到 0，必然优先选择删除 \boldsymbol{i \sim n} 行中较大的块（因为这样能以最少的删除块数达成目标）。

考虑贪心，维护一个最小堆，存储每一行完成操作 1 的至多 m 个较大方块（无法完成也没事，答案最大值就是 m，可剪枝为当下最优解 ans），同时更新堆的和 sum 和元素个数 cnt。

时间复杂度 O(nm\log{m})。

流程

• 从下往上遍历二维数组。

• 建立最小堆的优先队列 q。

• 将 a_{i,j} 放入 q。

  • 若 sum - q.top() \geq v_i 或者 cnt > ans，则不断弹出堆顶（最小值）。

• 所有进出队列操作记得维护 sum 和 cnt 。

• 细节注意 \texttt{long long} 。

代码

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int>v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    vector<vector<int>> a(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    priority_queue<int, vector<int>, greater<int> >q;
    ll sum = 0, cnt = 0, ans = m;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            q.push(a[i][j]);
            cnt ++; sum += a[i][j];
            while (cnt > ans || sum - q.top() >= v[i]) {
                sum -= q.top(); q.pop(); cnt--;
            }
            if (sum >= v[i])ans = min(ans, cnt);
        }
    }
    cout << ans << endl;
}
signed main() {
    io; int t = 1; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}