题解：P15541 [CCC 2026 S1] Baby Hop, Giant Hop

lsc_shenyin · 2026-03-07 08:55:28 · 题解

题目大意

给出 a，b，k（-10^{18} \le a,b \le 10^{18}，2 \le k \le -10^{18}），每一步操作可以使 a 加减 1 或加减 k，给出一个 t，当 t=1 时，输出将 a 变成 b 的最少步数，当 t=2 时，输出将 a 变成 b 的次少步数。

题目思路

考虑先处理 t=1 的情况，假设 a<b（如果 a>b，将操作的正负取反，即加变减、减变加，总操作次数不变），很显然，只有两种情况，设 n=\lfloor \frac {b-a}{k} \rfloor，m=(b-a) \mod k，则这两种情况为：b=a+nk+m 或 b=a+(n+1)k-(k-m)，第一种的操作次数为 n+m，第二种为 n+1+k-m，取较小者即可。

接下来分析 t=2 的情况，大致可以分为三种情况:

• 当 n+m \ne n+1+k-m 时，次少步数可能是较大者。
• 可以选择先加 1 再减 1，增加两步。
• 如果至少用过一次加减 k 的操作，便可以将其中一个加减 k 转化为 k 个加减 1，增加 k-1 步。

在以上三种情况找最小者即可。

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define the_end return 0;

ll a,b,k,t,ans,tmp,ma=1e18;

int main(){

    cin>>a>>b>>k>>t;
    ans=abs(b-a)/k;
    tmp=abs(b-a)%k;
    if(t==1)cout<<min(ans+tmp,ans+1+(k-tmp));
    else {
        if(ans+tmp!=ans+1+(k-tmp))ma=max(ans+tmp,ans+1+(k-tmp));//情况一
        ma=min(ma,min(ans+tmp,ans+1+(k-tmp))+2);//情况二，选择最小者加两步，因为步数较大的再加两步不可能成为第二大
        if(ans!=0)ma=min(ma,ans+tmp+(k-1));//情况三
        ma=min(ma,ans+1+(k-1)+(k-tmp));//情况三
        cout<<ma;
    }
    the_end
}