A22619. 公平
填空题
困难
知识点
题目描述
公平
题目描述
有多干所精英学院和 N 名天才学员（编号 1 到 N）。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。
联盟定期进行学员调院操作（共 Q 次）：第 j 次操作将学员 Cj 调到学院 Dj。
联盟公平指数定义为：
对每所至少有一名学员的学院，取该学院最高能力值；再取这些最高能力值中的最小值。
请计算每次调院操作后的联盟公平指数。
输入格式
第一行：N Q
接下来 N 行：每行 Ai Bi，表示学员 i 的能力值和初始学院
接下来 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×105，1 ≤ N,Q ≤ 2×105
1 ≤ Ai ≤ 109，1≤ Ai ≤ 109
1 ≤ Cj≤ N，1≤ Cj ≤ N
1 ≤ Bi, Dj ≤2×105，1≤ Bi, Dj ≤2×105
输入均为整数，每次转园操作会改变所属学院
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<int> ability(N + 1);
vector<int> current_college(N + 1);
unordered_map<int, multiset<int>> college_students;
for (int i = 1; i <= N; ++i) {
int A, B;
cin >> A >> B;
ability[i] = A;
current_college[i] = B;
college_students[B].insert(A);
}
multiset<int> global_max;
for (const auto& pair : college_students) {
const auto& s = pair.second;
if (!s.empty()) {
global_max.insert(*s.rbegin());
}
}
while (Q--) {
int Cj, Dj;
cin >> Cj >> Dj;
int c = Cj;
int a = ability[c];
int old_college = current_college[c];
int new_college = Dj;
// 处理旧学院
auto& old_set = college_students[old_college];
int x = *old_set.rbegin();
auto it_old = old_set.find(a);
old_set.erase(it_old);
if (old_set.empty()) {
auto it_global = global_max.find(x);
if (it_global != global_max.end()) {
global_max.erase(it_global);
}
college_students.erase(old_college);
} else {
int x_new = *old_set.rbegin();
if (x_new != x) {
auto it_global = global_max.find(x);
if (it_global != global_max.end()) {
global_max.erase(it_global);
}
global_max.insert(x_new);
}
}
// 处理新学院
auto& new_set = college_students[new_college];
bool was_empty = new_set.empty();
int y = 0;
if (!was_empty) {
y = *new_set.rbegin();
}
new_set.insert(a);
int y_new = *new_set.rbegin();
if (was_empty) {
global_max.insert(y_new);
} else {
if (y_new != y) {
auto it_global = global_max.find(y);
if (it_global != global_max.end()) {
global_max.erase(it_global);
}
global_max.insert(y_new);
}
}
current_college[c] = new_college;
cout << *global_max.begin() << '\n';
}
return 0;
}
上一题
下一题