CF1463C
感谢大查Qn帮我找出了inf设小的问题
直接模拟:
对于所有的指令,分为被忽略和不被忽略两种情况:
对于没被忽略的指令,只需要到达时间在下一条指令发布之前就行
对于被忽略的指令,除了要符合时间,还要求目标点在当前位置和当前正在执行指令的目标点之间;
所以要记录当前指令的一些数据:结束时间(用于判断下一个命令会不会被忽略),方向和目标位置(用于反推被忽略的指令发布时机器人的位置);
讲完了,根据条件模拟即可:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int T, n, ans, t[N], x[N], f1, f2, w; //f1存结束时间,f2存方向,w存位置
signed main(){cin >> T;while(T--){memset(t, 0 ,sizeof(t));ans = 0; w = 0; f1 = 0; f2 = 0; //多测不清空,__________cin >> n;t[n+1] = 1e18; //inf开大点!(再次感谢cqn)for(int i = 1; i <= n; i++) cin >> t[i] >> x[i];for(int i = 1; i <= n; i++){if(t[i] >= f1){ //发布时间晚于上个被执行的命令的结束时间,说明不被忽略f1 = t[i] + abs(w - x[i]); //更新新命令结束时间if(f1 <= t[i+1]) ans++; //满足条件,答案加一if(w <= x[i]) f2 = -1; //向右走(后面是反推位置,所以方向反着记)else f2 = 1; //向左走w = x[i]; //更新位置}else{ //被忽略int nw = w + (f1 - t[i]) * f2; //根据时间反推当前位置if(((x[i] - nw) * (x[i] - w) <= 0) && (t[i] + abs(nw - x[i]) <= t[i+1])) ans++;} //满足两个条件,答案加一}cout << ans << endl;}return 0;
}