P16703 [SEATST 2026] 两场考试 / Two Exams

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

``` N A[0] A[1] ... A[N - 1] B[0] B[1] ... B[N - 1] ```

一个整数，表示 `minimum_dissatisfaction` 的返回值。

### 样例 考虑以下函数调用： ```cpp minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1]) ``` 在这个例子中，一种分配新排名的方式是 $P = [0, 2, 3, 4, 1]$。 考虑学生 $1$ ，其 $P[1] = 2$ 。所有满足 $P[j] < P[1]$ 的学生 $j$ 在数学上的排名都比学生 $1$ 好，因此该学生满足班级排名条件。 接下来考虑学生 $2$ ，其 $P[2] = 3$ 。所有满足 $P[j] < P[2]$ 的学生 $j$ 在中文上的排名都比学生 $2$ 好，因此该学生也满足班级排名条件。 可以验证，所有其他学生同样满足班级排名条件。 这个新排名的不满意度为 $1$ 。不存在不满意度更低的其他新排名方案，因此该函数应返回 $1$ 。 ### 约束 - $1 \le N \le 5\ 000\ 000$。 - 对于所有 $0 \le i \le N - 1$ ， $0 \le A[i], B[i] \le N - 1$ 。 - 对于所有 $0 \le i < j \le N - 1$ ， $A[i] \ne A[j]$ 。 - 对于所有 $0 \le i < j \le N - 1$ ， $B[i] \ne B[j]$ 。 ### 子任务 1. （$3$ 分） $N \le 8$ 。 2. （$4$ 分） $N \le 20$ 。 3. （$13$ 分） $N \le 500$ 。 4. （$12$ 分） $N \le 3000$ ，且对于所有 $0 \le i \le N - 1$ 有 $A[i] + B[i] = N - 1$ 。 5. （$19$ 分） $N \le 3000$ 。 6. （$15$ 分） $N \le 100\ 000$ ，且对于所有 $0 \le i \le N - 1$ 有 $A[i] + B[i] = N - 1$ 。 7. （$17$ 分） $N \le 100\ 000$ 。 8. （$17$ 分）没有额外的约束。 **注**：对于子任务 $8$ ，仅评测程序就保证会占用 $3000$ 毫秒时间限制中的 $1500$ 毫秒。