B4045 [语言月赛 202410] 同桌

Igallta · 2024-11-26 14:27:42 · 题解

简要题意

给你一个 n 和一个数组 p，如果 p_{p_i}\not=i（i 期望同桌的期望同桌不是 i，那么此时 i 就不满意）或者 p_i=i，那么输出 No。否则输出 Yes。

思路

首先，我们肯定要输入。

这个地方因为不关课桌的事，所以可以直接给 n 乘 2。这部分的代码：

cin>>n;
n*=2;

然后，我们要输入 p 数组。在这里我们就可以判断 p_i 是否的等于 i 了，如果是直接输出 No 并结束程序的运行。

这部分的代码：

for(int i=1;i<=n;i++){
    cin>>want[i];//这里的 want 就是 p 数组 
    if(want[i]==i){
        cout<<"No";
        return 0;
    }
}

为什么不能边输入边判断 p_{p_i}\not=i 呢？因为次数只输入了 i 个数据，如果 p_i > i 那么因为 C++ 全局变量的特性，p_{p_i} 会等于 0。

所以，接下来我们要到单独用一个循环去判断 p_{p_i}\not=i。还是跟前面一样，只要有就直接输出 No 并结束程序。

最后，如果前面都没有结束那么最后还要输出 Yes 哦！

这部分的代码：

for(int i=1;i<=n;i++){
    if(want[want[i]]!=i){
        cout<<"No";
        return 0;
    }
}
cout<<"Yes";