520 钻石争霸赛 2021 7-7 约会大作战

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;
}





上一篇:03-键盘输入和屏幕输出


下一篇:第十一届山东省大学生程序设计竞赛(正式赛) BCDGH