【暑期每日一題】洛穀 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;
}