题解：P11533 [NOISG 2023 Finals] Topical

· · 题解

解题思路

第一眼看到 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，来决定循环是否终止。

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