自动搬运

查看原文

来自洛谷，原作者为

	lzt415 (Q≧w≦Q)

搬运于2025-08-24 23:08:09，当前版本为作者最后更新于2025-02-06 15:45:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

第一眼看到 $1\leq n, k\leq 10^6$ 时心中一颤，感觉不妙，结果第二眼一看，看到 $n\cdot k\leq 10^6$ 就明白这题大概要干什么了。

考虑维护一个 $n$ 行 $k$ 列的 $01$ 矩阵，维护当前的 $p_{j}$。矩阵中，如果 $r_{i,j} \leq p_{j}$，则 $a_{i,j}$ 赋值为 $1$，否则为 $0$。并且对于矩阵的每一行，维护这一行的和 $sum_{i}$。

怎样降低时间复杂度呢？我们先把矩阵每一列按值排序。

那么注意到，当 $p_{j}$ 增大时，会修改矩阵中的第 $j$ 列上前面一段连续的元素的值，把 $0$ 改为 $1$。当然，这个修改暴力一下即可。

好，为什么复杂度是正确的呢？很明显，$p_{j}$ 单调不降，我们已经先把每一列按值排序过了，所以每一个元素我们只会修改一次，故复杂度是可行的。

修改的同时维护 $s_{i}$ 也是简简单单，每次将此处元素的值从 $0$ 修改到 $1$，$s_{i}$ 就加上 $1$。当 $s_{i}$ 变为 $k$，意味着这场考试可以被完成，那么按照我刚刚说的方式更新 $p_{j}$，再更新 $s_{i}$ 然后在更新 $p_{j}$，以此类推。直到不再有 $s_{i}$ 变为 $k$。

不难发现刚刚的过程实现需要用到 while 循环和一个布尔变量判断是否有有 $s_{i}$ 变为 $k$，来决定循环是否终止。

好了，讲完了，这道题代码很短，就懒得呈现了，或者可以参考其他题解的代码，当然，推荐自己手写。