274D

MinCat · 2023-07-29 13:43:28 · 题解

我们只在意他们的大小关系，离散化每行的数字，然后 -1 的部分是无影响的，去除。把递增关系转化为有向边，小的往大的连，用拓扑排序求出其线性顺序，这就是答案了。如果有环的话，逻辑上就是有冲突，那就可以宣称无解。

但是这样做边太多了。如下图。

我们发现一些边其实是没用的，去掉也不影响拓扑序，只需要保留第一个比它小的边。

注：翻译好像有歧义，应该是改变矩阵列的顺序。我一开始还以为是填空。