二路归并
1934. 贝茜放慢脚步
题目大意：
事件包含两种，一种是到了减速时间，一种是到了减速距离，每发生一个事件速度会减慢，问贝茜滑完一千米所需的总时间
思路：
我们需要知道时间，就要知道速度，就必须知道当前发生了多少事件。所以需要将距离和时间统一单位，可以统一到时间上。
我们将减速时间存储到数组 $a$ 中，将减速距离存到数组 $b$ 中。
假设目前的时间是 $t$ ,目前走了距离 $s$ ，速度是 $v$ ，下一个减速时间是 $ a_i$ ,下一个减速距离是$b_j$,那么到下一个减速时间还剩 $a_i - t$ ，到下一个减速距离还剩的时间是 $\frac{b_j - s}{v}$，需要用二路归并的算法，将到时间的减速和到距离的减速统一到一个时间轴上。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10010;
int n;
vector<int> a, b;
int main()
{
cin >> n;
char str[2];
int x;
while (n -- )
{
scanf("%s%d", str, &x);
if (*str == 'T') a.push_back(x);
else b.push_back(x);
}
//设置终点距离是1000
b.push_back(1000);
//对时间和距离排序
sort(a.begin(), a.end());
sort(b.begin(), b.end());
//记录当前的时间、距离、速度，其中v表示速度的倒数，这样每次减速只需将v+1
double t = 0, s = 0, v = 1;
int i = 0, j = 0;
while(i < a.size() || j < b.size()){
//当距离走完了或是接下来减速时间先于减速距离到来
if (j == b.size() || i < a.size() && a[i] - t < (b[j] - s) * v){
//更新当减速时间到来时的距离，并更新当前时间
s += (a[i] - t) / v;
t = a[i];
v ++ ;
i ++ ;
}
else{
//要先更新时间，在更新距离，否则b[j] - s = 0
t += (b[j] - s) * v;
s = b[j];
v ++;
j ++;
}
}
printf("%.0lf\n",t);
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com
