Busy Robot

题意

机器人初始在一数轴上的原点 某时刻接受命令 并朝命令方向前进 每秒前进1距离 在未到达当前命令的终点时 忽略当前时刻的其他命令 若机器人在 $[t_i,t_{i+1}]$ 时间内移动到 $x_i$ 位置 视为完成一次指令 (被忽略的命令可能会成功执行)

给出一系列的指令问机器人能完成多少次

思路

记录每次指令的起点 $st$ 和终点 $ed$ 下一次停止的时间 $net$ 上一次接收到可执行命令的时刻 $las$

遍历每个指令 如果当前指令的时刻大于等于 $net$ 说明可以执行当前指令 更新 $net、st、ed、las$

否则判断机器人是否能在 $[t_i,t_{i+1}]$ 时间内移动到 $x_i$ 位置 具体判断依据为 在 $t_i$ 时刻 到 $t_{i+1}$ 时刻 机器人是否经过 $x_i$

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;

inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
typedef long long LL;
typedef pair<int, int>PII;
const int N = 100100;

int n;
LL tim[N];
LL pos[N];

void solve() {
   
	cin >> n;
	for (int i = 0; i < n; ++i) {
   
		cin >> tim[i] >> pos[i];
	}
	tim[n] = 1e10;

	LL net = 0; //下一次停止的时间
	LL st = 0, ed = 0; //一次指令的起点和终点
	LL las = 0; //上一次接收到命令的时间
	LL res = 0;

	for (int i = 0; i < n; ++i) {
   
		if (tim[i] >= net) {
   
			net = tim[i] + abs(pos[i] - ed);
			st = ed, ed = pos[i];
			las = i;
			if (net <= tim[i + 1])
				res++;
		}
		else {
   
			if (st >= ed) {
   
				int y = st - (tim[i] - tim[las]);
				int x = max(ed, st - (tim[i + 1] - tim[las]));
				if (pos[i] >= x && pos[i] <= y)res++;
			}
			else {
   
				int x = st + (tim[i] - tim[las]);
				int y = min(ed, st + tim[i + 1] - tim[las]);
				if (pos[i] >= x && pos[i] <= y)res++;
			}
		}
	}
	cout << res << endl;
}
int main() {
   
	int t; cin >> t;
	while (t--)
		solve();

	return 0;
}