题解：P14222 [ICPC 2024 Kunming I] 收集硬币

· · 题解

前置

传送门

AC记录

题目分析

本题要求我们在一个长度为 10^9 的网格上放置两个机器人，它们以相同的最大速度 v 移动，需要收集所有在特定时间和位置出现的硬币。我们需要找到最小的速度 v，使得能够收集所有硬币。

关键观察 时间顺序：硬币按时间顺序出现，且每个硬币的出现时间和位置都是唯一的。

机器人移动：每秒机器人可以移动到距离不超过 v 的任意格子。

收集条件：只有当机器人在硬币出现的同一时间位于同一格子时，才能收集硬币。

思路

核心算法：二分答案 + 可行性检查。

我们使用二分搜索来寻找最小的速度 v：

下界：l = 0；

上界：r = 10^9。

对于每个候选速度 v，我们需要检查是否存在一种机器人移动方案能够收集所有硬币。

可行性检查算法

在 check(v) 函数中，我们维护两个机器人的可能位置范围 [l, r]，并按照时间顺序处理硬币：

初始化：第一个硬币出现时，两个机器人都必须能够到达该位置，所以初始范围是 [1, 10^9]。

让我们不妨处理每个硬币：

  1. 计算时间差 T = t_i - t_p（t_p 是上一个处理的硬币时间）；

  2. 计算最大移动距离 d = T \times v。

我们需要检查两种情况：

情况1：一个机器人从上一个硬币位置移动到当前硬币位置是否可行；

情况2：另一个机器人在当前位置范围内是否能够到达当前硬币位置。

更新位置范围：

  1. 如果两种情况都满足，更新范围取交集；

  2. 如果只有一种情况满足，相应更新范围；

  3. 如果两种情况都不满足，返回不可行。

边界处理：确保位置范围始终在 [1, 10^9] 内。

复杂度为 O(n \log(10^9))。

Code

#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const int N=1e6+5;
const ll INF=1e9;
int n;
P a[N];
bool ck(P x,P y,ll v){
    return abs(x.se-y.se)<=v*abs(x.fi-y.fi);
} 
bool check(int v){
    int p=1;
    ll l=1,r=INF;
    for(int i=2;i<=n;i++){
        ll T=a[i].fi-a[p].fi,d=T*v;
        bool x=ck(a[i],a[p],v),y=(l-d<=a[i].se&&a[i].se<=r+d);
        if(x&&y){
            l=min(l-d,a[p].se-d);
            r=max(r+d,a[p].se+d);
        }else if(x){
            l=l-d;
            r=r+d;
        }else if(y){
            l=a[p].se-d;
            r=a[p].se+d;
        }else return 0;
        p=i;
        l=max(1ll,l);
        r=min(INF,r);
    }
    return 1;
}