专栏文章

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

hhyc42_Happiness
P14222题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minlql62
此快照首次捕获于
2025/12/02 04:28
3 个月前
此快照最后确认于
2025/12/02 04:28
3 个月前
查看原文

前置

传送门
AC记录

题目分析

本题要求我们在一个长度为 10910^9 的网格上放置两个机器人，它们以相同的最大速度 vv 移动，需要收集所有在特定时间和位置出现的硬币。我们需要找到最小的速度 vv，使得能够收集所有硬币。
关键观察 时间顺序：硬币按时间顺序出现，且每个硬币的出现时间和位置都是唯一的。
机器人移动：每秒机器人可以移动到距离不超过 vv 的任意格子。
收集条件：只有当机器人在硬币出现的同一时间位于同一格子时，才能收集硬币。

思路

核心算法：二分答案 + 可行性检查。
我们使用二分搜索来寻找最小的速度 vv：
下界：l=0l = 0；
上界：r=109r = 10^9。
对于每个候选速度 vv，我们需要检查是否存在一种机器人移动方案能够收集所有硬币。

可行性检查算法

在 check(v) 函数中，我们维护两个机器人的可能位置范围 [l,r][l, r]，并按照时间顺序处理硬币：
初始化：第一个硬币出现时，两个机器人都必须能够到达该位置，所以初始范围是 [1,109][1, 10^9]。
让我们不妨处理每个硬币：
  1. 计算时间差 T=ti−tpT = t_i - t_p（tpt_p 是上一个处理的硬币时间）；
  2. 计算最大移动距离 d=T×vd = T \times v。
我们需要检查两种情况：
情况1：一个机器人从上一个硬币位置移动到当前硬币位置是否可行；
情况2：另一个机器人在当前位置范围内是否能够到达当前硬币位置。
更新位置范围：
  1. 如果两种情况都满足，更新范围取交集；
  2. 如果只有一种情况满足，相应更新范围；
  3. 如果两种情况都不满足，返回不可行。
边界处理：确保位置范围始终在 [1,109][1, 10^9] 内。
复杂度为 O(nlog⁡(109))O(n \log(10^9))。

Code

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

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...