7-7 约会大作战
题目
某社团开展了一个“快闪”相亲活动,活动规则如下:
(1)社团负责人将所有人分为两组,并收集了每个人对另外一组的所有人的好感度;
(2)然后社团负责人会随机地在两组各抽取一个人,询问他们是否愿意一起去约会;
(3)所有人对一开始的两次询问一定会拒绝;
(4)从第三次询问开始,如果询问的人的好感度大于这个人之前的两个没能牵手的人,则接受,否则拒绝;
(5)只有两个人同时接受,约会才成立。
(6)约会成立后,后面的询问一律拒绝。
现在给出好感度和每次询问的两个人,请你帮忙计算一下最终有哪些人可以去约会了。
输入格式:
输入第一行是三个数字 N,M,Q (1 ≤ N,M ≤ 100, 1 ≤ Q ≤ 500), 表示分成的两组里,第一组有 N 个人,第二组有 M 个人,共有 Q 次询问。
接下来 N 行,每行 M 个数,第 i 行的第 j 个数表示第一组的第 i 个人对第二组的第 j 个人的好感度数值。数字的绝对值不超过 100。
再接下来的 M 行,每行 N 个数,第 i 行的第 j 个数表示第二组的第 i 个人对第一组的第 j 个人的好感度数值。数字的绝对值同样不超过 100。
最后有 Q 行,每行两个数字 x,y,表示主持人询问第一组的第 x 个人和第 y 个人去不去约会。
每一组内人的编号从 1 开始。
注意: 如果同一对人被询问两次,会被当成两对人处理。
输出格式:
输出若干行,每行两个数 a,b,表示第一组的第 a 个人和第二组的第 b 个人约会成功。顺序按照询问顺序的先后。如果没有一对能约会成功,则输出一行 PTA is my only love
。
输入样例:
3 4 12
8 9 1 2
3 4 8 5
1 8 2 9
8 6 2
8 4 1
5 8 7
7 2 8
3 1
2 3
3 3
1 3
2 1
1 4
1 1
2 4
3 2
2 2
1 2
3 4
输出样例:
1 1
3 4
题解
(注:仅供参考,如有疑问,勿喷)
/**
* @Time :2021-05-21-19.30
* @Author :Yang JiaBin
* @version :V 1.0
* @desc :
*
*/
#include<bits/stdc++.h>
using namespace std;
int love1[105][105];//第一组对第二组人的好感度
int love2[105][105];//第二组对第一组人的好感度
int prior_a[105];//第一组上一次没约成的人的好感度
int prior_b[105];//第二组上一次没约成的人的好感度
int sum_a[105];//第一组的人没约成的次数
int sum_b[105];//第二组的人没约成的次数
bool vis_a[105];//标记第一组的人是否约成了
bool vis_b[105];//标记第二组的人是否约成了
int N,M,Q;
int main(){
cin>>N>>M>>Q;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
cin>>love1[i][j];
}
}
for(int i=1;i<=M;i++){
for(int j=1;j<=N;j++){
cin>>love2[i][j];
}
}
vector< pair<int,int> > ans;//用于记录答案
int x,y;
for(int i=0;i<Q;i++){
cin>>x>>y;
//如果没约成功,以下是没约成功的条件
if( sum_a[x]<2 || sum_b[y]<2 //询问次数小于2次
|| love1[x][y]<=prior_a[x] || love2[y][x]<=prior_b[y] //这一次的好感度没有大于上一次
|| vis_a[x] || vis_b[y]){ //已经约会成功了
sum_a[x]++;//询问次数累加
sum_b[y]++;
prior_a[x] = love1[x][y];//好感度更新
prior_b[y] = love2[y][x];
}else{
vis_b[y] = vis_a[x] = true;//标记约会成功
ans.push_back((pair<int,int>){x,y});//配对成功,加进数组
}
}
if(ans.empty()){
cout<<"PTA is my only love";
}else{
for(int i=0;i<ans.size();i++){
cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
}
return 0;
}