Blog - Floating Ocean
0%

FjnuOJ - 第四场世纪大战 - 带佐的回家路

发表于 更新于
本文字数： 688 阅读时长 ≈ 1 分钟
阅读次数： Valine：

原题：https://fjnuacm.top/d/contest/p/29?tid=635bad6e691055e12dce5282

题意

带佐在数轴上。 时刻，带佐位于 处。在时刻 和 之间的时间段中，带佐要么待在当前位置，要么向左或向右跳 个单位长度。输出带佐最早在哪个时刻可以到达 。

思路

首先，结论是：首项为 ，公差为 的等差数列的前 项和满足 的最小 即为答案。

下面给出证明思路：

  1. 上述结论的做法是：

    令 满足条件的最小，，则只需在 时刻停留即可保证最后一步恰好走到 。

  2. 上述结论的合理性：

    ① 我们不可能折回，因为折回后如果直接返回，只能前进 ，代价大于在 时刻停留的代价（可以根据等差数列理解，列方程来严格证明），而停留后返回代价明显更大（停留需要很长时间，而折回后返回前进的距离远没有这么长）。

    ② 我们不可以停留太久，显然停留一次比停留多次代价小。

因此，用一个 轻松解决。

值得注意的是，上述证明不严密。

对应AC代码

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        long x = scanner.nextLong(), t = 0, i = 1;
        while(t < x){
            t += i;
            i ++;
        }
        System.out.println(i - 1);
    }
}

暴力就完事了