[CF1463C] Busy Robot

[CF1463C] Busy Robot

Description

机器人在一维坐标轴上移动。你可以给这个机器人下达指令，指令的形式为 (t_i), (x_i) ,意味着机器人在第 (t_i) 秒的时候获得一条指令，此时这个机器人以 (1/s) 的速度从现在的位置开始向 (x_i) 移动。若机器人执行当前指令的过程中收到其他命令那么忽略。现在问你给出的指令中被成功执行的命令有几条，条件为：假设当前命令为 t_i, x_i , 若机器人在 t_i 到 t_{i+1}这个时间区间（包括边界）内到达过 x_i 这个位置，则称这条命令被成功执行。

Solution

我们始终维护当前的目标位置，对于一个命令，我们先判断是否能接受它（即当前是否以及处于当前目标位置，如果不等于则需要继续向着这个目标走，否则，我们就用新的命令的目标替换当前目标），然后我们通过当前时间和下面一条命令进来的时间之间的差值来判断这条命令能否被完成

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        vector<pair<int, int>> vec(n + 2);
        for (int i = 1; i <= n; i++)
            cin >> vec[i].first >> vec[i].second;

        int current_time = -1;
        int current_target = 0;
        int current_pos = 0;

        vec[n + 1].first = 1e12;
        vec[n + 1].second = 0;

        vector<int> fin(n + 2);

        for (int i = 1; i <= n; i++)
        {
            // cout << "time = " << vec[i].first << " pos=" << current_pos << endl;
            auto [new_time, new_target] = vec[i];
            int succ_flag = 0;
            if (current_target == current_pos) // accept
            {
                current_target = new_target;
                succ_flag = 1;
            }
            int step = min(vec[i + 1].first - vec[i].first, abs(current_pos - current_target));
            int current_pos_ = current_pos;
            if (current_pos < current_target)
                current_pos_ += step;
            else
                current_pos_ -= step;
            if ((((current_pos <= new_target) && (current_pos_ >= new_target) && current_pos <= current_pos_) ||
                 ((current_pos_ <= new_target) && (current_pos >= new_target) && current_pos_ <= current_pos)))
            {
                fin[i] = 1;
            }
            current_pos = current_pos_;
        }

        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans += fin[i];

        cout << ans << endl;
    }
}