题解：P12892 [蓝桥杯 2025 国 Java B] 弹跳鞋

· · 题解

思路

水一篇题解。

容易发现不会有无解的情况：充能 2L，前跳，后跳，前跳，后跳......每两步造成 1 的位移，最终总位移为 L。

我们要求最少充能的能量。显然充能 x，最多可以向前跳 \frac{x(x+1)}{2} 这么远。我们要选择在向前跳了这么远的基础上，选择一些步骤，把它们从向前跳改成向后跳。设选择的步骤跳跃长度之和是 y，那么我们要让 \frac{x(x+1)}{2}-2y=L，即 y=(\frac{x(x+1)}{2}-L)\div2。

我们有一个结论：对于 1 到 \frac{x(x+1)}{2} 中的所有整数 y，都是可以取若干个不同的数使它们和为 y 的。为什么？\ 事实上当我们只有 1,2,4,8,\cdots 可选的时候就可以根据 y 的二进制表示来取到 y 了，现在我们有 1,2,3,4,5,\cdots,x，显然也能取到。

但是上述有合法的 y 的前提条件是 y 是个整数，所以 (\frac{x(x+1)}{2}-L) 得是一个偶数。打表可以发现 \frac{x(x+1)}{2} 的奇偶性以“奇奇偶偶奇奇偶偶”为循环节循环，所以我们可以二分出最小的 x' 使得 \frac{x'(x'+1)}{2}\ge L，再暴力向上找最小的 x\ge x' 使 \frac{x(x+1)}{2} 与 L 奇偶性相同，根据循环节我们知道 x-x'\le 2。

二分上界是 O(\sqrt{L})，时间复杂度 O(\log L)。

代码

Java 代码编写过程中使用了生成式 AI 作为辅助工具。

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        long L = scanner.nextLong();
        long l = 1,r = 2000000000;
        while(l < r){
            long mid = (l + r) / 2;
            if(prefix_sum(mid) >= L) r = mid;
            else l = mid + 1;
        }
        while(prefix_sum(l) % 2 != L % 2) l ++;
        System.out.println(l);
    }
    private static long prefix_sum(long x){
        return x * (x + 1) / 2;
    }
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
long long L,l,r,mid;
inline long long preffix_sum(long long x){
    return x * (x + 1) / 2;
}
int main(){
    scanf("%lld",&L);
    l = 1,r = 2e9;
    while(l < r){
        mid = (l + r) / 2;// (l+r) 会超过 int 范围 
        if(preffix_sum(mid) >= L) r = mid;
        else l = mid + 1;
    }
    while(preffix_sum(l) % 2 != L % 2) l ++;
    printf("%d\n",l);
    return 0;
}