题解：CF2253D Hypercarp and Interdimensional Jumps

· · 题解

CF2253D 题解

思路

每一次跳动都会让某个分量的速度 +1，而这个速度会对后续的跳动产生影响。

那么我们考虑，一次操作造成的速度 +1 会导致最终路程发生什么变化。

很显然，若总共操作 t 次，那么第 1 次操作会对坐标分量贡献 t 的路程，第 2 次操作贡献 t-1 的路程，依此类推。

那么我们枚举 t 表示总共操作 t 次，然后对于 t,t-1,t-2,\cdots,1，依次减到剩余较大的坐标分量中，即可构造出答案。

但是这样会超时，因此我们考虑二分这个 t，找到最大的一个合法 t，然后根据这个 t 来构造答案。因为如果 t 更大，就会超出范围，不可行。

赛时没考虑太多，把超出范围的结果记为 +\infty，然后写了个三分，其实这里二分就能过的，因为函数是单调减的，我们只要最后一个符合条件的，就是最优解。

代码

https://codeforces.com/contest/2253/submission/386104476