简答题
偏难
#13122
公平 题目描述 有多干所精英学院和 N 名天才学员(编号 1 到 N)。每名学员 i拥有能力值 A i 和初始所属学院 Bi。 联盟定期进行学员调院操作(共 Q…
公平
题目描述
有多干所精英学院和 N 名天才学员(编号 1 到 N)。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。
联盟定期进行学员调院操作(共 Q 次):第 j次操作将学员 Cj 调到学院 Dj。
联盟公平指数定义为:
对每所至少有一名学员的学院,取该学院最高能力值;再取这些最高能力值中的最小值。
请计算每次调院操作后的联盟公平指数。
输入格式
· 第一行: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×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
输入均为整数
每次转园操作会改变所属学院
限制
时间限制:1000ms
内存限制:256MiB
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。