Codeforces - 1463C. Busy Robot (思维)

简介: 笔记

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;
}


目录
相关文章
|
机器人
hdu1035 Robot Motion(简单模拟题)
hdu1035 Robot Motion(简单模拟题)
38 0
|
人工智能
Codeforces-Adding Powers(进制问题+思维)
Codeforces-Adding Powers(进制问题+思维)
91 0
|
机器学习/深度学习
AtCoder Beginner Contest 218 F - Blocked Roads (最短路径还原 思维)
AtCoder Beginner Contest 218 F - Blocked Roads (最短路径还原 思维)
98 0
|
机器学习/深度学习 人工智能 BI
Educational Codeforces Round 115 (Rated for Div. 2) D. Training Session(组合数学 思维)
Educational Codeforces Round 115 (Rated for Div. 2) D. Training Session(组合数学 思维)
107 0
HDOJ 1339 A Simple Task(简单数学题,暴力)
HDOJ 1339 A Simple Task(简单数学题,暴力)
113 0
下一篇
无影云桌面