A21385. 小美参加的编程夏令营引入了新的导师分配系统：系统配置：有 m 位导师（编号 1 - m）和 n 位学生（编号 1 - n）每位学生提交两个不同的导师志愿（ai 和 bi）分配规则（按学生编号顺序处理）：首先尝试分配第一志愿导师 ai。如果该导师未被选中，则成功分配，否则尝试第二志愿 bi如果第二志愿导师未被选中，则成功分配 如果两个志愿导师都已被选中，则该学生分配失败一旦导师被分配给某…
填空题
较难
知识点
题目描述
题目描述
小美参加的编程夏令营引入了新的导师分配系统：
系统配置：
有 m 位导师（编号 1 - m）和 n 位学生（编号 1 - n）
每位学生提交两个不同的导师志愿（ai 和 bi）
分配规则（按学生编号顺序处理）：
首先尝试分配第一志愿导师 ai。如果该导师未被选中，则成功分配，否则尝试第二志愿 bi
如果第二志愿导师未被选中，则成功分配
如果两个志愿导师都已被选中，则该学生分配失败
一旦导师被分配给某个学生，就不能再分配给其他学生
对于每位学生i，需要回答:
"如果只从第i位学生开始按顺序处理到最后一位学生(即i~n号学生)，最终会有多少人能成功分配到导师?
特别注意:
每个查询相互独立，即考虑不同的初始状态-导师一旦被分配就不可再选
输入格式
输入第一行是两个整数 n, m，分别表示同学数量和教练数量（教练编号为 1 - m）。
接下来 n 行，每行包含两个整数 ai, bi，含义如题。
输出格式
输出 n 行，每行包含一个整数表示第 i 个同学应该给出的答案。
样例输入
4 2
1 2
1 2
1 2
1 2样例输出
2
2
2
1样例解释
对1号学生的查询:
1选1号导师(成功)
2选2号导师(成功)
3、4号无法选择
→答案2
对2号学生的查询:
2选1号导师(成功)
3选2号导师(成功)
4号无法选择
→答案2
对3号学生的查询：
3选1号导师(成功)
4选2号导师(成功)
→答案2
对4号学生的查询:
4选1号导师(成功)>答案
参考答案
#include<bits/stdc++.h>
using namespace std;
/*panda*/
#define pb push_back
#define fs first
#define sc second
#define f(i,a,b) for(int i = a;i<=b;++i)
#define f_(i,a,b) for(int i = a;i>=b;--i)
typedef long long ll;
#define pii pair<ll,ll>
typedef unsigned long long ull;
const int N =1e5+10;
int n,m,res,v[N];
pii p[N];
int ans[N],k;
//处理第x个学生的分配情况
void wk(int x){
if(v[p[x].fs]==0){
v[p[x].fs]=x;
res++;
return ;
}
//如果第一志愿被占令且能挤走
if(v[p[x].fs]>x){
int t = v[p[x].fs];
v[p[x].fs] = x;
wk(t);
return ;
}
if(v[p[x].sc]==0){
v[p[x].sc]=x;
res++;
return ;
}
if(v[p[x].sc]>x){
int t = v[p[x].sc];
v[p[x].sc] = x;
wk(t);
return ;
}
}
void solve(){
cin>>n>>m;
f(i,1,n){
cin>>p[i].fs>>p[i].sc;
}
f_(i,n,1){
wk(i);
ans[i]=res;
}
f(i,1,n)cout<<ans[i]<<endl;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int _ = 1;
// cin>>_;
while(_--)solve();
return 0;
}
上一题
下一题