logo AlgoBeat OnlineJudge
登录 注册

#216693. [SEATST 2026] 两场考试 / Two Exams

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

班级里有 名学生。每名学生根据当前的班级排名被分配了一个从 的编号。也就是说,学生 (对于所有 )当前的班级排名为 。在这里,排名 是最好的,而排名 是最差的。

班上最近考完中文和数学考试。学生 (对于所有 )在中文考试中排名 ,而在数学考试中排名 均是长度为 的排列。

:::info[什么是长度为 的排列?]{open} 在本题中,长度为 的排列 是一个长度为 的数组,满足对于所有 ,且对于所有

例如, 是一个长度为 的排列,但 不是长度为 的排列。 :::

老师想对所有学生进行重新排名。新的排名可以用一个排列 来表示。

对于每位学生 ,新的班级排名必须满足至少以下一个条件:

  • 对于所有满足 ,学生 的中文成绩好于学生 (即 ),或
  • 对于所有满足 ,学生 的数学成绩好于学生 (即 )。

:::warning[警告]{open} 该条件仅适用于满足 。对于满足 则没有任何限制。

对于每位学生 ,在评估其是否满足条件时,必须首先选择一门学科,然后用该学科与所有对应的学生 进行比较。对于同一个 ,所有不同的 必须在同一门学科上优于学生 。你不能在为学生 评估条件时中途切换学科。 :::

新班级排名的不满意度定义为所有学生中排名下降的最大幅度。换句话说,不满意度即为 (对于所有 )的最大值。

:::warning[警告]{open}

不满意度是 的最大值, 的值不会影响不满意度的计算。 :::

在所有可能的新排名中,请找出最小可能的不满意度

实现详情

你需要实现以下函数:

int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B)
  • :学生人数。
  • :一个长度为 的数组,表示中文考试的排名。
  • :一个长度为 的数组,表示数学考试的排名。
  • 此函数应返回新班级排名的最小不满意度。
  • 此函数在每个测试数据中恰好被调用一次。

输入格式

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

输出格式

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

数据范围与提示

样例

考虑以下函数调用:

minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1])

在这个例子中,一种分配新排名的方式是

考虑学生 ,其 。所有满足 的学生 在数学上的排名都比学生 好,因此该学生满足班级排名条件。

接下来考虑学生 ,其 。所有满足 的学生 在中文上的排名都比学生 好,因此该学生也满足班级排名条件。

可以验证,所有其他学生同样满足班级排名条件。

这个新排名的不满意度为 。不存在不满意度更低的其他新排名方案,因此该函数应返回

约束

  • 对于所有
  • 对于所有
  • 对于所有

子任务

  1. 分)
  2. 分)
  3. 分)
  4. 分) ,且对于所有
  5. 分)
  6. 分) ,且对于所有
  7. 分)
  8. 分)没有额外的约束。

:对于子任务 ,仅评测程序就保证会占用 毫秒时间限制中的 毫秒。