简答题

公平

题目描述

有多干所精英学院和 N 名天才学员（编号 1 到 N）。每名学员 i拥有能力值 A_i 和初始所属学院 Bi。

联盟定期进行学员调院操作（共 Q 次）：第 j次操作将学员 C_j 调到学院 D_j。

联盟公平指数定义为：

对每所至少有一名学员的学院，取该学院最高能力值；再取这些最高能力值中的最小值。

请计算每次调院操作后的联盟公平指数。

输入格式

· 第一行：N Q

· 接下来 N 行：每行 Ai Bi，表示学员 ii 的能力值和初始学院

· 接下来 Q 行：每行 Cj Dj，表示将学员 Cj 调到学院 Dj

输出格式

· Q 行：每行一个整数，表示每次操作后的公平指数

输入样例#1

6 3

8 1

6 2

9 3

1 1

2 2

1 3

4 3

2 1

1 2

输出样例#1

6

2

6

输入样例#2

2 2

4208 1234

3056 5678

1 2020

2 2020

输出样例#2

3056

4208

说明提示

1≤N,Q≤2×10⁵，1≤N,Q≤2×10⁵

1≤A_i≤10⁹，1≤A_i≤10⁹

1≤C_j≤N，1≤C_j≤N

1≤B_i,D_j≤2×10⁵，1≤B_i,D_j≤2×10⁵

输入均为整数

每次转园操作会改变所属学院

限制

时间限制：1000ms

内存限制：256MiB

使用微信搜索喵呜刷题，轻松应对考试！

答案：

这是一个涉及动态变化和计算公平指数的问题，具体答案需要结合代码实现，简要思路如下：

首先，需要处理输入数据，读取学员的数量N、操作次数Q、学员的能力值Ai和初始学院Bi等信息。
维护两个关键的数据结构：一个存储每个学院的最高能力值（max_ability），一个存储每个学员当前所在的学院（school）。在第一次操作时，初始化这两个数据结构。
对于每次操作，更新学员所在学院，并更新对应学院的最高能力值。同时，记录每次操作后的公平指数。计算公平指数时，先找到所有有学员的学院，在这些学院的最高能力值中取最小值即为公平指数。
输出每次操作后的公平指数。

解析：

【答案】这道题目是一道涉及动态变化和计算公平指数的题目，需要处理大量的数据并维护一些关键的数据结构来计算公平指数。具体的实现细节较为复杂需要根据题目的要求和输入数据的特性来设计算法并进行优化。这里只能提供一个大致的思路和框架代码供您参考和进一步扩展实现。在实现过程中需要注意处理边界条件和异常情况以确保程序的正确性和稳定性。同时还需要注意时间复杂度和空间复杂度的优化问题以确保程序的效率和性能满足题目要求。

创作类型：

原创

本文链接：公平题目描述有多干所精英学院和 N 名天才学员（编号 1 到 N）。每名学员 i拥有能力值 Ai

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！