班级里有 名学生。每名学生根据当前的班级排名被分配了一个从 到 的编号。也就是说,学生 (对于所有 )当前的班级排名为 。在这里,排名 是最好的,而排名 是最差的。
班上最近考完中文和数学考试。学生 (对于所有 )在中文考试中排名 ,而在数学考试中排名 。 和 均是长度为 的排列。
:::info[什么是长度为 的排列?]{open}
在本题中,长度为 的排列 是一个长度为 的数组,满足对于所有 有 ,且对于所有 有 。
例如, 是一个长度为 的排列,但 和 不是长度为 的排列。
:::
老师想对所有学生进行重新排名。新的排名可以用一个排列 来表示。
对于每位学生 ,新的班级排名必须满足至少以下一个条件:
- 对于所有满足 的 ,学生 的中文成绩好于学生 (即 ),或
- 对于所有满足 的 ,学生 的数学成绩好于学生 (即 )。
:::warning[警告]{open}
该条件仅适用于满足 的 。对于满足 的 则没有任何限制。
对于每位学生 ,在评估其是否满足条件时,必须首先选择一门学科,然后用该学科与所有对应的学生 进行比较。对于同一个 ,所有不同的 必须在同一门学科上优于学生 。你不能在为学生 评估条件时中途切换学科。
:::
新班级排名的不满意度定义为所有学生中排名下降的最大幅度。换句话说,不满意度即为 (对于所有 )的最大值。
:::warning[警告]{open}
不满意度是 的最大值, 的值不会影响不满意度的计算。
:::
在所有可能的新排名中,请找出最小可能的不满意度。
实现详情
你需要实现以下函数:
int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B)
- :学生人数。
- :一个长度为 的数组,表示中文考试的排名。
- :一个长度为 的数组,表示数学考试的排名。
- 此函数应返回新班级排名的最小不满意度。
- 此函数在每个测试数据中恰好被调用一次。