题目
https://codeforces.com/contest/1463/problem/C
思路
模拟，设$nowpos$为当前时刻的位置，$nextpos$为下一时刻的位置，如果对于第$i$个命令，存在$nowpos\leq pos_i\leq nextpos$或$nextpos\leq pos_i\leq nowpos$（反方向移动时），则这一命令为有效命令。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
#define endl '\n'
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define lowbit(x) (x&-x)
using namespace std;
struct _IO { _IO() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); } }_io;
typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll;
const ll maxn = 1e5 + 5;
ll n, t[maxn], pos[maxn];
int main()
{
ll T;
cin >> T;
while (T--)
{
ll ans = 0;
cin >> n;
for (ll i = 1; i <= n; ++i) cin >> t[i] >> pos[i];
t[n + 1] = 1e18;
ll nowpos = 0, t_ = 0, dir = 0, ind = 0;
for (ll i = 1; i <= n; ++i)
{
if (t_ <= t[i]) t_ += abs(nowpos - pos[i]) + abs(t_ - t[i]), dir = pos[i] - nowpos, ind = i;
ll nextpos;
if (dir > 0) nextpos = min(nowpos + t[i + 1] - t[i], pos[ind]);
else nextpos = max(nowpos + t[i] - t[i + 1], pos[ind]);
if ((nowpos <= pos[i] && pos[i] <= nextpos) || (nextpos <= pos[i] && pos[i] <= nowpos)) ++ans;
nowpos = nextpos;
}
cout << ans << endl;
}
return 0;
}
|