AcWing 每日一题 2022/4/29【1968. 奶牛赛跑】
为了解决谁是跑的最快的奶牛的长期争论，贝茜和艾希决定在农场中来一场赛跑。
两头奶牛在同一时间从同一地点出发，朝同一方向奔跑。
每个奶牛的奔跑过程都可以划分为若干段。
在每一段行程中，奶牛的奔跑速度相同。
例如，贝茜可能首先以 5 的速度奔跑 3 单位时间，然后以 10 的速度奔跑 6 单位时间。
贝茜和艾希的总跑步时间相同。
两头奶牛希望你帮助计算在她们的赛跑中，领头者的变化次数。
当上一次的领头者是 B 的情况下，如果 A 超过了 B，成为了领头者，那么领头者的变化就发生了。
例如，如果 B 是领头者，然后 A 超过了 B，这就算是一次领头者的变化。
如果 B 是领头者，然后 A 追上了 B 并与他齐头并进一段时间，最终 A 超过了 B，这也算是一次领头者的变化。
输入格式
第一行包含两个整数 N 和 M，表示贝茜的奔跑过程可分为 N 段，艾希的奔跑过程可分为 M 段。
接下来 N 行，每行描述一段贝茜的奔跑过程，包含两个整数，分别表示贝茜的奔跑速度以及她以这个速度奔跑的时间（两个整数都在 1…1000 范围内）。
接下来 M 行，每行描述一段艾希的奔跑过程，包含两个整数，分别表示艾希的奔跑速度以及她以这个速度奔跑的时间（两个整数都在 1…1000 范围内）。
输出格式
输出赛跑中领头者的变化次数。
数据范围
1≤N,M≤1000
输入样例：
4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9
输出样例：
2
样例解释
t<3 时，艾希保持领先位置。
t=3 时，贝茜追上艾希，并以相同速度奔跑一个单位时间。
随后贝茜提速，超过艾希（第一次领头者变化）。
短暂时间后，艾希提速，超过贝茜（第二次领头者变化）并保持领先至结束。
题目分析
N和M的大小都是1000
对于每一组数据v和t的大小也都是<=1000
因此我们可以暴力计算出贝茜和贝茜分别在每一个单位时间上的位置，通过比较两个人位置的变化情况，来判断领头者是否发生了改变
时间复杂度为O(106)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1000010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int idx;
int a[N], b[N];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i ++ )
{
int v, t;
cin >> v >> t;
while(t -- )
{
a[idx ++ ] = v;
}
}
idx = 0;
for(int i = 0; i < m; i ++ )
{
int v, t;
cin >> v >> t;
while(t -- )
{
b[idx ++ ] = v;
}
}
int res = 0;
int flag = 0;
int la = 0, lb = 0;
for(int i = 0; i < idx; i ++ )
{
la += a[i];
lb += b[i];
if(la > lb)
{
if(flag == 2)
res ++ ;
flag = 1;
}
if(la < lb)
{
if(flag == 1)
res ++ ;
flag = 2;
}
}
cout << res << endl;
return 0;
}
