【暑期每日一题】洛谷 P1568 赛跑

题目链接：P1568 赛跑 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

赛跑

题目描述

SH的跑步成绩一直不太理想。为了帮助SH提高成绩，KC决定和他进行一次赛跑。比赛的起点设在农场主的屋前，他们同时出发，沿着同一方向，直到跑到终点----农场远处的一棵树下。

他们的跑步速度在一些时间段内是恒定的。比如：SH在前３个时间段速度是５，接着６个时间段内速度是１０。他们的比赛总时间相同。他们希望能统计出在整个比赛过程中领先顺序的变化次数。举个例子，某个时刻SH领先，下个时刻KC领先，这就是一次领先顺序的变化；如果某个时刻SH领先，接下来一段时间KC赶上来并和SH齐头并进，但最终还是超过了SH，这也是一次领先顺序的变化。

输入格式

第１行：N和M（1 <= N, M <= 1000）。

接下来的N行：每行两个整数，描述SH跑步的一段，分别表示该段SH跑步的速度和持续这种速度的时间。所有的数据范围 [1..1000]。

再接下来的M行：每行两个整数，描述KC跑步的一段，分别表示该段KC跑步的速度和持续这种速度的时间。所有的数据范围 [1..1000]。

输出格式

一行：整个比赛过程中领先顺序的变化次数。

样例 #1

样例输入 #1

4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9

样例输出 #1

2

提示

输入：SH在前２个单位时间内速度是１，接着１个单位时间内速度是４，接着１个单位时间内速度是１，最后１０个单位时间内速度是２。KC在前３个个单位时间内速度是２，接着２个单位时间内速度是１，最后9个单位时间内速度是３。

输出：比赛开始后KC领先，直到第５个单位时间SH超过KC（第一次领先顺序变化），接着第７个单位时间时，KC又反超SH，变成领先（第二次领先顺序变化）。

AC code:（注意一定要开long long！！！）

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
	typedef long long ll;
	vector<ll> s1,s2;
	ll n,m;
	cin>>n>>m;
	ll s=0;
	while(n--)
	{
		ll a,b;
		cin>>a>>b;
		while(b--)
		{
			s+=a;
			s1.push_back(s);
		}
	}
	
	s=0;
	while(m--)
	{
		ll a,b;
		cin>>a>>b;
		while(b--)
		{
			s+=a;
			s2.push_back(s);
		}
	}
	
	//i+1                1 2 3 4 5 6  7  8  9  10 11 12 13 14
	//s1[i]              1 2 6 7 9 11 13 15 17 19 21 23 25 27
	//s2[i]              2 4 6 7 8 11 14 17 20 23 26 29 32 35
	//s2[i]-s1[i]        1 2 0 0 -1 0 1  2  3  4  5  6  7  8
	
	ll cnt=0;
	vector<ll> res;
	for(ll i=0;i<s1.size();i++)
	{
		if(s1[i]!=s2[i]) // 路程差(s2[i]-s1[i])==0不放入 
			res.push_back(s2[i]-s1[i]);
	}

	for(ll i=1;i<res.size();i++)
		if(res[i]*res[i-1]<0)
			cnt++;
	
	cout<<cnt;
	
	return 0;
}