题解 CF2252C Risky Tower

JuRuoOIer · 2026-08-10 08:38:11 · 题解

题解 CF2252C Risky Tower

同场其他题

题意

给定 n\times m 的矩阵 a 和长为 n 的数组 v。删除 a_{i,j} 后 v_1,\dots,v_i 均会减少 a_{i,j}。你需要删除若干个格子，直到存在 v_i\le 0 或者某一行被删完，求至少要删除多少个。

数据范围：多测，\sum nm\le 10^6。

做法

做过《P9168 [省选联考 2023] 人员调度》可能有所帮助。

:::info[我毫无头绪。] 试着对每个 v_i 求出至少需要删多少个格子才能使其变得 \le 0。 :::

:::info[该如何优化？] 我们发现除了 v_i\le 0 以外还有一种方法可以完成操作——删空一整行。这意味着答案不大于 m。 :::

先看提示。

所以我们只需要从下往上枚举每行，并维护当前行及以下的前 m 大即可。这样增加一行的复杂度是 O(m\log m)。

单组复杂度 O(nm\log m)。