题目链接

1934. 贝茜放慢脚步

奶牛贝茜正在参加冬季哞林匹克运动会的越野滑雪比赛。

她以每秒 \(1\) 米的速度出发。

但是，随着时间的推移，她变得越来越疲倦，她开始放慢脚步。

每次放慢脚步，贝茜的速度都会降低：减速一次后，她以每秒 \(1/2\) 米的速度移动，减速两次后，则以每秒 \(1/3\) 米的速度移动，依此类推。

你将被告知何时何地贝茜会减速。

当减速信息格式为：

T 17

意味着，贝茜在某个时间点减速，本例表示比赛开始第 \(17\) 秒贝茜减速。

当减速信息格式为：

D 10

意味着，贝茜在某个地点减速，本例表示在行进 \(10\) 米处减速。

给定 \(N\) 个减速信息，请计算贝茜滑完一千米需要多少秒。

将你的答案四舍五入到最接近的整数（ \(0.5\) 向上舍入为 \(1\)）。

输入格式

第一行包含整数 \(N\)。

接下来 \(N\) 行，每行描述一个减速信息，格式为 T x 或 D x。

无论哪种情况，\(x\) 都是一个整数，保证所有减速都在贝茜滑完一千米前发生。

可能同时发生多次减速，那么这会使得贝茜的速度一下子变慢很多。

所有减速信息不一定按顺序给出。

输出格式

输出贝茜滑完一千米所需的总时间。

数据范围

\(1≤N≤10000\)

输入样例：

2
T 30
D 10

输出样例：

2970

样例解释

贝茜以每秒 \(1\) 米的速度跑完前 \(10\) 米，耗时 \(10\) 秒。

然后她减速到每秒 \(1/2\) 米，接下来的 \(10\) 米要花 \(20\) 秒。

然后她在第 \(30\) 秒时，再次减速到每秒 \(1/3\) 米。

滑完剩下的 \(980\) 米需要 \(980×3=2940\) 秒。

因此，总时间是 \(10+20+2940=2970\) 秒。

解题思路

二路归并

将时间和地点分为两个数组并排序，并用两个指针分别指向时间和地点，判断哪个时间或地点时间更短或更近，走更短或更近的那个，并移动指针更新当前走过的时间以及距离和速度·，最后再以某一速度走到终点

• 时间复杂度：\(O(n)\)

代码

// Problem: 贝茜放慢脚步
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1936/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

// %%%Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=10005;
int n;
char op;
double a[N],b[N];
int p1,p2;
int main()
{
	scanf("%d",&n);
	while(n--)
	{
		double x;
		getchar();
		scanf("%c %lf",&op,&x);
		if(op=='T')a[++p1]=x;
		else
			b[++p2]=x;
	}
	sort(a+1,a+1+p1);
	sort(b+1,b+1+p2);
	double time=0,dis=0,speed=1;
	a[p1+1]=b[p2+1]=1e9;
	for(int i=1,j=1;i<=p1||j<=p2;)
	{
		if((a[i]-time)*(1./speed)<b[j]-dis)
		{
			dis+=(a[i]-time)*(1./speed);
			time=a[i];
			speed++;
			i++;
		}
		else
		{
			time+=(b[j]-dis)/(1./speed);
			dis=b[j];
			speed++;
			j++;
		}
	}
	time+=(1000-dis)/(1./speed);
	printf("%.lf",time);
	return 0;
}