P12732 外人 题解

· · 题解

题目大意

一共有 n 节课，n-1 个课间。每节课两人分别在 y[i] 和 s[i] 上课，到了课间便会分别从 y[i] 和 s[i] 转移至 y[i+1] 和 s[i+1]。问两人一共会在几个课间互相见到。

解题思路

题意晦涩难懂，不妨画个图先来理解。

下面以样例为例画个图：

3       // 3 节课
1 2 3 // y[i]
3 1 2 // s[i]

这大概就阐述清了“如果他们同时间处于同一高度，也就是说如果上述两条线段有交点，那么两人就会互相见到”的含义。

那还有一个“他们可以在两层之间的楼梯上见到，也可以在出发时或到达时见到”，啥意思？

《生动形象》。

这就很好考虑了，判断每个线段是否有交点即可。

核心内容

判断交点，可以通过比较线段端点的方法来判断。

由第一幅图可知：如果 s[i] < y[i]，且 s[i+1] > y[i+1]，则两条线段有交点；
由第二幅图可知：第一个课间时，如果 s[i] < y[i]，且 s[i+1] = y[i+1]，则两条线段端点相交；第二个课间时，如果 s[i] = y[i]，则两条线段端点也相交。

整理，得：s[i] < y[i] 且 s[i+1] \ge y[i+1] 或 s[i] = y[i] 时，两线段有交点。

由于咱们不知道 s[i] 和 y[i] 谁大，所以判断的时候需要判断两次。

最后 ans 计数输出即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n;
int s[10005],y[10005];
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>s[i];
    for(int i=1;i<=n;i++)   cin>>y[i];
    for(int i=1;i<=n-1;i++)
    {
        //核心部分
        if(s[i]>y[i]&&y[i+1]>=s[i+1]||y[i]>s[i]&&s[i+1]>=y[i+1]||s[i]==y[i])    ans++;
    }
    cout<<ans;
    return 0;
}

感谢观看。