首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; using namespace std; int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     int N, Q;     cin &gt;&gt; N &gt;&gt; Q;     vector&lt;int&gt; ability(N + 1);     vector&lt;int&gt; current_college(N + 1);     unordered_map&lt;int, multiset&lt;int&gt;&gt; college_students;     for (int i = 1; i &lt;= N; ++i) {         int A, B;         cin &gt;&gt; A &gt;&gt; B;         ability[i] = A;         current_college[i] = B;         college_students[B].insert(A);     }     multiset&lt;int&gt; global_max;     for (const auto&amp; pair : college_students) {         const auto&amp; s = pair.second;         if (!s.empty()) {             global_max.insert(*s.rbegin());         }     }     while (Q--) {         int Cj, Dj;         cin &gt;&gt; Cj &gt;&gt; Dj;         int c = Cj;         int a = ability[c];         int old_college = current_college[c];         int new_college = Dj;         // 处理旧学院         auto&amp; 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&amp; 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 &lt;&lt; *global_max.begin() &lt;&lt; '\n';     }     return 0; }</pre>
这道题暂未补解析。