自动搬运

查看原文

来自洛谷，原作者为

	Mss1617 记得做做题哦！|| 虽然不像头像那么含蓄，但她其实挺真实的 || 最后在线时间: 2025/8/24 23:06

搬运于2025-08-24 23:17:47，当前版本为作者最后更新于2025-06-07 18:05:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

一共有 $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;
} 

感谢观看。