L2-028 秀恩爱分得快 (25 分)

最新推荐文章于 2022-10-20 09:36:42 发布

lovesickman

最新推荐文章于 2022-10-20 09:36:42 发布

阅读量672

点赞数 1

分类专栏： PAT天梯文章标签：算法 c++

本文链接：https://blog.csdn.net/hacker__man/article/details/123582354

版权

PAT天梯专栏收录该内容

21 篇文章

订阅专栏

这篇博客介绍了一个C++程序，用于解决一个情侣牵手问题。程序涉及到字符串读入、数组处理、亲密度计算以及查找最佳匹配。博主分享了在处理过程中遇到的错误和优化代码的方法，包括计算异性亲密度的函数以及打印结果的函数。文章还包含了完整的代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

处理起来非常麻烦的一道题。

尤其是必须区别 +0 和 -0，这要求所有的读入都必须是字符串读入。

整理下思路：

sex[] 存储每个人的性别，atoi 将字符串转成int。先把所有的M张照片存储下来。读入一对情侣。

两次遍历所有的照片，分别求出两个人a/b 和其他异性的亲密度，存储在gra[1010]数组中，用下标检索，求最值。

~~天梯赛中的题，很多都是浪费空间节省检索数组的时间，因为一般数组都不会开很大。~~

TMD 我麻了

for(int i=0;i<m;i++){
    int num;cin>>num;
    for(int i=0;i<num;i++){// 用了两个i，找了20分钟bug，我是SB
        cin>>c;
        int x=abs(atoi(c));
        if(c[0]=='-')sex[x]=1;
        p[i].pb(x);
    }
}

别人的代码中使用了两个函数简化了代码，一个是计算x和他的异性亲密度的，还有print函数,还有传引用得到k，以及使用sex[a]^sex[b]表示a和b是异性都很棒。

/*
18点29分
*/
#include<iostream>
#include<cstring>
#include<vector>
#define pb push_back
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
const int N =1e3+10;
int n,m,a,b;
int A,B;
int sex[N];//sex[i]=1,表示编号为i的人是女性
vector<int>p[N];
/*
18点32分 写完了读入，开始计算和a是异性的所有人的亲密度
*/
double cala[N],calb[N];
/*
然后就是一个分支，
我的思路都是求出和a是异性的亲密度的最大值，然后再去搜，这里别人的题解是直接存下
cala数组中哪个位置是和a亲密度最大的
*/
void print(int a,int b){
    if(sex[a])cout<<"-";
    cout<<a<<" ";
    if(sex[b])cout<<"-";
    cout<<b<<endl;
}

void Print(int c,double a[],int k){
    for(int i=0;i<n;i++){
        if(a[i]==a[k]){
            print(c,i);
        }
    }
}

bool cal(int a,int b,double ca[],int &k)//找a的，a的原配是b，存入ca数组，k是最大值的下标,并判断找到的元素是不是b
{
    for(int i=0;i<m;i++){
        //先看看照片中有没有a，没有的话就跳过
        int j=0;
        for(;j<p[i].size();j++){
            if(p[i][j]==a)break;
        }       
        if(j>=p[i].size())continue;
        for(j=0;j<p[i].size();j++){
            if(sex[p[i][j]]^sex[a]){
                ca[p[i][j]]+= 1.0/p[i].size();
            }
        }
    }
    double maxn=-1;
    for(int i=0;i<n;i++){
        if(ca[i]>maxn){
            maxn=ca[i];
            k=i;
        }
    }
    if(ca[b]==ca[k]){
        return 1;
    }
    return 0;
}

int main(){
    cin>>n>>m;
    char c[20];
    for(int i=0;i<m;i++){
        int num;cin>>num;
        for(int j=0;j<num;j++){
            cin>>c;
            int x=abs(atoi(c));
            if(c[0]=='-')sex[x]=1;
            p[i].pb(x);
        }
    }
    cin>>c;
    a = abs(atoi(c));
    if(c[0]=='-') sex[a]=1;
    
    cin>>c;
    b = abs(atoi(c));
    if(c[0]=='-') sex[b]=1;
    bool e = cal(a,b,cala,A);
    bool f = cal(b,a,calb,B);
    if(e&&f){
        print(a,b);
    }
    else{
        Print(a,cala,A);
        Print(b,calb,B);
    }
    return 0;
}