Busy Robot
题意
机器人初始在一数轴上的原点 某时刻接受命令 并朝命令方向前进 每秒前进1距离 在未到达当前命令的终点时 忽略当前时刻的其他命令若机器人[ t i , t i + 1 ]时间内移动到xi位置 视为完成一次指令 (被忽略的命令可能会成功执行)
给出一系列的指令问机器人能完成多少次
思路
记录每次指令的起点 st 和终点 ed 下一次停止的时间 net 上一次接收到可执行命令的时刻las
遍历每个指令 如果当前指令的时刻大于等于 n e t netnet 说明可以执行当前指令 更新net、st、ed、las
否则判断机器人是否能在 [ t i , t i + 1 ] 时间内移动到 x i 位置 具体判断依据为 在 ti时刻到 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; }
